Case Study of the Proof of Cook's theorem - Interpretation of A(w)
classification
💻 cs.CC
keywords
cooktheoremproblemcasepolynomialprooftime-verifiableappearance
read the original abstract
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 propositional formula A(w) to simulate a computation of TM, and such A(w) is claimed to be CNF to represent a polynomial time-verifiable problem w. In this paper, we investigate A(w) through a very simple example and show that, A(w) has just an appearance of CNF, but not a true logical form. This case study suggests that there exists the begging the question in Cook's theorem.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.