pith. sign in

arxiv: 1905.06311 · v1 · pith:AWPCYLGVnew · submitted 2019-04-30 · 💻 cs.OH

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

classification 💻 cs.OH
keywords machinep-reductionbeencookturingdefinitionmightoracle
0
0 comments X
read the original abstract

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 of NDTM from Oracle machine to Turing machine. The definition or derivation of P-reduction is essentially equivalent to Turing's computability. Whether NP problems might been reduced to logical forms (tautology or SAT) or NP problems might been reduced each other, they have not been really proven in Cook's 1971 paper.

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.