[FOM] Cognitive biases in the proof of Cook's theorem?

[Timothy Y. Chow]

Cas Barla wrote:
> In a series of recent papers, Jianming Zhou and Yu Li have argued :
>
> Cook's theorem is the origin of the loss of nondeterminism in terms 
> of the equivalence of the two definitions of NP, the one defining NP as 
> the class of problems solvable by a nondeterministic Turing machine in 
> polynomial time, and the other defining NP as the class of problems 
> verifiable by a deterministic Turing machine in polynomial time. 
> Therefore, we argue that fundamental difficulties in understanding P 
> versus NP lie firstly at cognition level, then logic level.
[...]
> I am wondering if the definition of class NP as in Cook's paper from 
> 1971 has already been questioned or even seriously challenged ?

I took a quick look at these papers.  They contain nothing resembling what 
I would consider to be accurate mathematical reasoning.

I do agree with them that the "N" in "NP" confuses a lot of people who 
haven't formally studied complexity theory and have picked up their 
knowledge of NP "on the street" so to speak.  That's about the only cogent 
observation I could find in what they have written.

Tim