2 citations · 5 across the 5 of their papers we have counts for
5 papers
Inquiry of P-reduction in Cook's 1971 Paper -- from Oracle machine to Turing machine
JianMing Zhou, Yu Li
In this paper, we inquire the key concept P-reduction in Cook's theorem and reveal that there exists the fallacy of definition in P-reduction caused by the disguised displacement o…
Case Study of the Proof of Cook's theorem - Interpretation of A(w)
Yu Li
Cook's theorem is commonly expressed such as any polynomial time-verifiable problem can be reduced to the SAT problem. The proof of Cook's theorem consists in constructing a propos…
Interpretation of NDTM in the definition of NP
JianMing Zhou, Yu Li
In this paper, we interpret NDTM (NonDeterministic Turing Machine) used to define NP by tracing to the source of NP. Originally NP was defined as the class of problems solvable in…
What is Cook's theorem?
JianMing Zhou, Yu Li
In this paper, we make a preliminary interpretation of Cook's theorem presented in [1]. This interpretation reveals cognitive biases in the proof of Cook's theorem that arise from…
What is NP? - Interpretation of a Chinese paradox "white horse is not horse"
Yu Li
The notion of nondeterminism has disappeared from the current definition of NP, which has led to ambiguities in understanding NP, and caused fundamental difficulties in studying th…