Abstract
This paper presents a conceptual critique of the foundational proof of Cook’s Theorem. It argues that the standard equivalence between the two definitions of NP—solvability by a nondeterministic machine and verifiability by a deterministic one—is based on a "cognitive bias." By deconstructing the logical gaps in the proof, the authors suggest that complexity theory has conflated distinct levels of computation, potentially obscuring the path to solving the P vs. NP problem.
Introduction
In computational complexity theory, the class NP is traditionally defined in two ways:
- Solvability: Problems solvable by a Nondeterministic Turing Machine (NDTM) in polynomial time.
- Verifiability: Problems whose solutions can be verified by a Deterministic Turing Machine (DTM) in polynomial time.
While textbooks treat these definitions as equivalent, the authors argue this is a "cognitive trap" originating in Stephen Cook’s 1971 paper. They contend that the current understanding of NP has effectively "erased" nondeterminism by reducing it to deterministic verification. This paper seeks to reveal the logical gaps in Cook’s Theorem to explain why the P vs. NP problem remains intractable.
Conceptual Deconstruction: The Query Machine
The authors perform a logical deconstruction of Cook’s proof, specifically examining the use of an "oracle" and a "query machine" to bridge the gap between NDTMs and DTMs. They argue that this introduces a theoretical hypothesis (the oracle) as a practical fact.
The paper claims Cook "discretely replaced" the NDTM with a DTM via the query machine. They argue that an oracle, which "instantly" knows a truth, and a DTM, which must compute it, exist at different "levels of reality." This substitution masks the fundamental difference between searching for a solution and verifying one.
The Loss of Nondeterminism
A central theme is the "loss of nondeterminism." By accepting the verifiability-based definition as the standard for NP, researchers have stopped investigating the unique properties of nondeterministic branching. Instead, nondeterminism is treated merely as a "guessed" input for a deterministic checker.
The authors point out that the construction of the Boolean formula $A(w)$ (the SAT instance) from a Turing machine's computation is a deterministic, polynomial-time process. Therefore, it inherently represents a deterministic verification rather than a truly nondeterministic search. They reference the classical Chinese paradox, "White horse is not horse," to argue that while verifiability (the white horse) belongs to the category of computation (horse), it is not identical to the general concept of nondeterministic solvability.
A Rectified Interpretation
The authors propose a "rectification" of complexity theory by splitting Cook's Theorem into two parts:
- Theorem 0: Any problem verifiable by a DTM can be represented as a SAT formula.
- Theorem 1': The "solvability" version is a consequence of Theorem 0, not an equivalent statement.
This concludes that the two definitions of NP are situated at different conceptual levels and have a "cause-effect" relationship rather than being logically identical.
Conclusion and Future Directions
The paper suggests that the difficulty of P vs. NP is not just a mathematical hurdle but a fundamental cognitive bias in our definitions. Future work should explore the problem through the lens of cognitive science and re-examine the essence of nondeterminism. By separating verifiability from solvability, a more robust definition might lead to a breakthrough in complexity theory.
Summary updated