- Interpretation of a Chinese paradox "white horse is not horse"
Abstract
This paper presents a philosophical critique of the complexity class NP, challenging the standard equivalence between its solvability-based and verifiability-based definitions. By applying the ancient Chinese paradox "white horse is not horse," the author argues that the current mathematical consensus suffers from a cognitive bias that obscures the true nature of nondeterminism, potentially explaining the enduring difficulty of the P vs. NP problem.
Introduction: The Conceptual Ambiguity of NP
The P vs. NP problem remains the most significant open question in theoretical computer science. At its core lies the definition of NP (Nondeterministic Polynomial time). Historically, NP was defined by solvability: the class of problems solvable by a nondeterministic Turing machine in polynomial time. However, modern pedagogy often replaces this with a verifiability-based definition: the class of problems whose solutions can be verified by a deterministic Turing machine in polynomial time.
While the academic community treats these definitions as interchangeable, this paper argues that the shift to verifiability strips away the essential concept of "nondeterminism." This transition creates a cognitive blind spot, making the P vs. NP problem fundamentally harder to grasp because researchers are conflating distinct levels of determinism and nondeterminism.
The "White Horse" Paradox and Cognitive Bias
To illustrate this confusion, the author invokes the ancient Chinese paradox "white horse is not horse" (proposed by Gongsun Long, c. 300 BC). In the paradox, a conflict arises because one party views a "white horse" through the lens of the general category "horse" (a deterministic view), while the other focuses on the specific attributes that distinguish "white horses" from the general set.
Similarly, in computer science, the "professional argument" suggests that a deterministic machine is merely a special case of a nondeterministic one (where the number of choices $n=1$). The author contends this is a logical deduction that fails at the cognitive level. Having one choice ($n=1$) is semantically different from having multiple choices ($n>1$). By defining NP through deterministic verification, we lose the ability to distinguish NP from P cognitively.
Academic Consensus and the P vs. NP Belief
Despite these conceptual hurdles, the belief that $P \neq NP$ has only strengthened over time within the research community, even as the foundational definitions remain conceptually murky.
*[What is NP?
- Interpretation of a Chinese paradox "white horse is not horse", page 3](/pdf/art_8e3b2c323bb3492db29d92e30dc8d2f9#page=3)*
As shown in the table above, the percentage of researchers believing $P \neq NP$ rose from 61% in 2002 to 83% in 2012. The author suggests that this overwhelming consensus, while perhaps mathematically intuitive, may be "question-begging" if the foundational definitions of the problem are misunderstood. If we cannot properly define "nondeterminism" without resorting to deterministic verifiability, our certainty in the separation of the classes may be built on a flawed cognitive framework.
Conclusion: Beyond Pure Logic
The barrier to solving P vs. NP may not be a lack of mathematical tools, but a fundamental misunderstanding of what a "problem" is. The author concludes that $NP \neq P_{verifiable}$ at a cognitive level. Resolving the millennium problem requires stepping back from pure formal logic to re-evaluate the foundational definitions of computation, potentially integrating Eastern philosophical perspectives to overcome Western cognitive biases.
Note: This paper is a theoretical critique and does not provide a formal mathematical proof.
Summary updated