Abstract
This research paper presents a critical inquiry into the foundational logic of NP-completeness as established in Stephen Cook’s seminal 1971 work. Authors JianMing Zhou and Yu Li argue that the definition of P-reduction contains a "fallacy of definition" or "disguised displacement." By examining the transition from theoretical, non-constructive Oracle machines to standard Turing machines, the authors suggest that the formal distinction between P and NP may lack the rigorous mathematical support traditionally assumed by the computer science community.
Introduction
The theory of NP-completeness, anchored by Cook’s Theorem, is a cornerstone of modern computer science. It posits that certain problems, like SAT, are representative of the entire class of Nondeterministic Polynomial time (NP) problems. However, despite decades of acceptance, a persistent "perplexity" remains regarding the "invisible fence" between P and NP. Zhou and Li address this gap by scrutinizing the original derivation of P-reduction, arguing that a logical "disguised displacement" occurred when transitioning from Oracle machines to Nondeterministic Turing Machines (NDTMs).
The Oracle Machine and P-reduction
In his 1939 work, Alan Turing defined an Oracle as an "omniscient logic"—a non-mechanical entity that provides answers instantly. Cook’s 1971 paper utilized "query machines" to define P-reduction. In this model, an input $w$ is processed by an Oracle that provides a solution $u$, which is then verified by a Turing Machine (TM).
The authors argue that this Oracle is fundamentally non-constructive. It represents a "black box" whose internal workings are not defined by standard mechanical computation. By treating the Oracle as a component that can be seamlessly integrated into a machine definition, the authors claim the proof glosses over the constructive process required to generate a solution.
The Critique: Disguised Displacement
The core of the authors' critique lies in how this Oracle was replaced by a "Guessing Module" in the definition of NDTMs. They argue that Cook’s proof assumes a solution $u'$ is provided to a checking module without justifying the constructive process of generating that solution.
According to Zhou and Li, treating an Oracle as a "guessing module" (which is essentially a tree of standard TM computations) effectively collapses the distinction between nondeterminism and determinism. Since every NDTM has an equivalent deterministic TM, they argue that treating them as interchangeable in the context of P-reduction effectively treats NP problems as if they were already proven to be computable in the same sense as P problems. This creates a circular logic where the reduction of NP problems to logical forms like SAT was never truly established.
Conclusion
The paper concludes that P-reduction, as defined by Cook, fails to provide unique mathematical support for NP-completeness because it essentially reduces to standard Turing computability. While this is a contrarian view that challenges fifty years of consensus, the authors position their inquiry as a necessary step to bridge the gap between classical complexity theory and modern fields like artificial intelligence. They call upon the academic community to re-examine the "dark ages" of complexity theory to ensure the logical foundations of the field are truly sound.
Summary updated