2 papers
cs.OH2019
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…
cs.CC2019
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…