Cognitive biases in the proof of Cook's theorem?

[Cas Barla]

In a series of recent papers,  Jianming Zhou<https://www.researchgate.net/scientific-contributions/2154297019_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. »



What is Cook's theorem?

https://www.researchgate.net/publication/270594335_What_is_Cook's_theorem


Inquiry of P-reduction in Cook's 1971 Paper -from Oracle machine to Turing machine

https://www.researchgate.net/publication/333174027_Inquiry_of_P-reduction_in_Cook's_1971_Paper_-from_Oracle_machine_to_Turing_machine


Case Study of the Proof of Cook's theorem - Interpretation of A(w)

https://www.researchgate.net/publication/332778876_Case_Study_of_the_Proof_of_Cook's_theorem_-_Interpretation_of_Aw


Interpretation of NDTM in the definition of NP

https://www.researchgate.net/publication/331485324_Interpretation_of_NDTM_in_the_definition_of_NP


What is NP? - Interpretation of a Chinese paradox "white horse is not horse"

https://www.researchgate.net/publication/270594425_What_is_NP_-_Interpretation_of_a_Chinese_paradox_white_horse_is_not_horse




I am wondering if the definition of class NP as in Cook’s paper from 1971 has already been questioned or even seriously challenged ?


Cas.


Provenance : Courrier<https://go.microsoft.com/fwlink/?LinkId=550986> pour Windows 10

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20200124/cb595c3d/attachment-0001.html>