Interpretation of NDTM in the definition of NP

JianMing Zhou, Yu LiarXiv 2019 · arXiv

Abstract

The P vs NP problem remains one of the most significant open questions in theoretical computer science. This paper argues that the difficulty in resolving it may stem from a fundamental "disguised displacement" in the definition of a Non-Deterministic Turing Machine (NDTM). By tracing the historical evolution of NP from Stephen Cook’s original oracle-based "Query Machine" to the modern "guess-and-check" verifier model, the authors highlight a logical gap. They contend that the modern verifier-based definition, while computationally convenient, loses the essence of nondeterministic decision-making and fails to maintain logical consistency, particularly regarding "no" instances of a problem.

Introduction

In standard computational complexity theory, the class NP (Nondeterministic Polynomial time) is typically introduced through two supposedly equivalent definitions. The first is solver-based: a problem is in NP if it can be solved by an NDTM in polynomial time. The second is verifier-based: a problem is in NP if a candidate solution (a certificate) can be verified by a deterministic Turing machine (DTM) in polynomial time. This paper challenges the validity of this equivalence, suggesting that the shift from the original oracle-based conception to the modern verifier-based one has introduced subtle but critical logical ambiguities.

The Oracle Model and the Original NDTM

The authors trace the genealogy of NP back to Stephen Cook’s seminal 1971 paper. In this original context, the NDTM was conceptualized as a "Query Machine" that utilizes an Oracle. This Oracle is not a standard computational component but a source of "transcendent judgment" that can provide an answer to a query instantly.

The Oracle-based Query Machine model

In this model, the machine's "essence" is its ability to consult an external authority. The nondeterminism lies in the machine's capacity to "know" which path to take or which query to make to reach an accepting state. This is fundamentally different from a physical machine performing step-by-step calculations.

The Disguised Displacement

The paper argues that a "disguised displacement" occurred in the late 1970s, popularized by texts like Garey and Johnson’s Computers and Intractability. The NDTM was redefined as a two-stage process: a "guessing module" that non-deterministically writes a string (the certificate) on a tape, and a "checking module" that deterministically verifies that string.

The authors claim this shift replaces the "essence" of the machine. The original Oracle-based model focuses on the decision of the problem instance, whereas the verifier model focuses on the verification of a specific string. This reduction of nondeterminism to a deterministic check of a pre-existing certificate, the authors argue, strips away the core concept of choosing the correct path among many possibilities.

Case Study: Graph Isomorphism

To illustrate the practical differences between these models, the authors examine problems like Graph Isomorphism (GI). In the verifier model, if we are given two graphs and a proposed mapping between their vertices, a DTM can easily check if the mapping is an isomorphism.

Comparison of graphs Gp1 and Gt1

However, the authors point out a logical inconsistency when dealing with "no" instances. If a guessed certificate is incorrect, the verifier simply fails to accept. But this does not constitute a definitive "no" decision for the problem instance itself (i.e., "these two graphs are definitely not isomorphic"). In the original Oracle-based model, the machine was intended to reach a definitive decision state ($q_Y$ or $q_N$). The verifier model’s inability to provide a symmetric "no" decision suggests it is not a true functional equivalent to the original decision-based NDTM.

Logical Implications and the P vs NP Problem

The core of the paper’s critique is that the "equivalence" between NDTMs and verifiers is a historical accident rather than a logical necessity. By treating them as identical, the field has introduced a "logic error" where the verification of a certificate is confused with the actual decision-making process.

This ambiguity has profound implications for the P vs NP problem. If the definition of NP itself is logically displaced or ill-posed, then the question "P = NP?" may be impossible to answer in its current form. The authors suggest that the difficulty in proving P ≠ NP might stem from the fact that we are comparing a class of deterministic machines (P) with a class (NP) whose definition has become logically inconsistent over time.

Conclusion

The authors advocate for a rigorous re-evaluation of the foundations of complexity theory. By tracing back to the work of Turing and Cook, researchers may be able to clarify the nature of nondeterminism and resolve the logical gaps introduced by the verifier model. Until the definition of NP is anchored in a consistent logical framework, the P vs NP problem may remain an intractable mystery born of definitional displacement.

Summary updated

BibTeX
@misc{zhou2019interpretation,
  author = {JianMing Zhou and Yu Li},
  title = {{Interpretation of NDTM in the definition of NP}},
  year = {2019},
  eprint = {1903.00355},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1903.00355},
}
Figure