What is Cook's theorem?

JianMing Zhou, Yu LiarXiv 2015 · arXiv

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:

  1. Solvability: Problems solvable by a Nondeterministic Turing Machine (NDTM) in polynomial time.
  2. 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 Query Machine with an Oracle versus a standard Deterministic Turing Machine.

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.

Comparison between a DTM with a guessing module and a true Nondeterministic Turing Machine.

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

BibTeX
@misc{zhou2015what,
  author = {JianMing Zhou and Yu Li},
  title = {{What is Cook's theorem?}},
  year = {2015},
  eprint = {1501.01910},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1501.01910},
}
Figure