Abstract:
When clues are absent, a deterministic Turing machine $M$ cannot deterministically solve an NP-complete problem in polynomial time. Doing so would violate the fundamental definition of a mathematical function and/or the second law of thermodynamics.
1. Introduction:
Is it possible to solve an NP-complete problem in polynomial time? Using the haystack analogy, is it possible to find the needle without using brute force—that is, sifting through every piece of straw? If one has a magnet, the needle could be drawn out instantly. However, that would require a powerful magnetic field capable of covering the entire haystack at light speed, which is analogous to parallel processing where multiple cores evaluate every element simultaneously. Because the P vs. NP question applies strictly to deterministic Turing machines that process a problem sequentially, parallel processing and the metaphorical magnet are ruled out. To avoid pure brute force, an algorithm analogous to a metal detector remains a viable option. Gradient descent mimics this approach, utilizing local feedback clues to efficiently navigate and narrow down the search space. Clues appear to be essential to solving a hard problem; although, they may not always be present or sufficient. In the sections below, we explore whether they are truly essential and whether a function or algorithm exists that can take the output of a Boolean satisfiability problem and return the satisfying assignment in polynomial time.
The Inverse Function
Cook-Levin Theorem. The Boolean satisfiability problem is NP-complete.
Let $\phi$ be a Boolean satisfiability instance in conjunctive normal form with $n$ variables. Here, $n \in \mathbb{N}$. The maximum runtime $t$ needed to solve $\phi$ via brute force is $O(2^n)$. There are $2^n$ possible truth-value assignments, but not all of them will satisfy $\phi$. Below is a list of the possible assignments:
\[\phi_{\text{assignments}} = \begin{pmatrix} x_1 & x_2 & \dots & x_I \\ 0 & 0 & \dots & 0 \\ 0 & 0 & \dots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \dots & 1 \end{pmatrix} \hspace{1 cm} (1)\]Assume that a satisfying assignment has been found using brute force:
\[ \phi(x_1, x_2, \dots, x_I) = \phi(0, 1, \dots, 0) = 1 \quad (1 \equiv \text{true}, \; 0 \equiv \text{false}) \hspace{1 cm} (2) \]Given this specific solution to $\phi$, assume it is possible to construct and verify an inverse function or algorithm denoted as $\phi^{-1}$:
\[ \phi^{-1}(1) = (0, 1, \dots, 0) \hspace{1 cm} (3) \]The inverse function $\phi^{-1}$ successfully returns the correct satisfying assignment in polynomial time when given the input $1$. The ultimate objective is to determine whether such an inverse mapping $\phi^{-1}$ can be generalized to efficiently find satisfying assignments for all Boolean satisfiability instances in polynomial time.
Let $\psi$ be a Boolean satisfiability instance distinct from $\phi$, such that $\psi$ has a unique satisfying assignment of $(1, 1, \dots, 1)$. If one attempts to use the previously defined inverse function $\phi^{-1}$ to find this assignment in polynomial time, a contradiction arises:
\[ \phi^{-1}(1) = (0, 1, \dots, 0) \neq (1, 1, \dots, 1) \hspace{1 cm} (4) \]Because $\psi(1, 1, \dots, 1) = 1$, evaluating $\phi^{-1}(1)$ yields an assignment that fails to satisfy $\psi$.
By the fundamental definition of a mathematical function, a single input cannot map to multiple distinct outputs. Consequently, the distinct instance $\psi$ requires its own unique inverse mapping, which can only be constructed and verified if the solution to $\psi$ is already known via brute force or an alternative search method. This requirement of prior knowledge undermines the utility of using a predetermined inverse function to solve new instances. It can be inferred that this limitation generalizes to all instances of the Boolean satisfiability problem and, by extension, any NP-complete problems to which they reduce.
Entropy
The Shannon entropy $H(X)$ is as follows:
\[ H(X) = - \sum_{i=1}^{N}p(x_i)\log_2(p(x_i)) \hspace{1 cm} (5) \]Where $X$ is the overall random event being analyzed; $p(x_i)$ is the probability of a specific individual outcome; $N \in \mathbb{N}$, is the number of specific individual outcomes. Assume $\phi$ is an instance reduced from the hardest NP-complete problem. We can express its maximum search space size in terms of Shannon entropy:
\[ H(X) = - \sum_{i=1}^{2^n}\frac{1}{2^n}\log_2(\frac{1}{2^n}) = -log_2(\frac{1}{2^n}) \hspace{1 cm} (6) \]Using the power rule of logarithms $(\mu \log(\nu) = \log(\nu^\mu))$:
\[ H = \log_2(2^n) \hspace{1 cm} (7) \]According to the second law of thermodynamics (SLOT), entropy stays the same or increases over time. To reduce the maximum runtime $O(2^n)$ to $O(n^k)$ requires a reduction of entropy:
\[ \ H < log_2(n^k) \hspace{1 cm} (8) \]where $k \in \mathbb{N}$ is a constant, where a search space of size $n^k$ can be traversed in polynomial time. The inequality at (8) illustrates why, given insufficient clues, no deterministic algorithm has been found that can solve NP-complete problems in polynomial time. Such an algorithm is prohibited from violating the SLOT.
Now, it is possible to increase the amount of order of a system, i.e., reduce its entropy by doing work on it, but disorder or entropy will increase elsewhere. We model this in the following manner:
\[ H = \log_2(n^k) + \log_2(2^n) - \log_2(n^k) + \epsilon \hspace{.5 cm}(\epsilon\geq 0) \hspace{1 cm} (9) \]Where $\epsilon$ is any increase in the overall entropy. The first term on the right side of equation (9) is reduced entropy that corresponds to a reduced search space of $n^k$. The remaining terms on the right side represent where entropy increases.
It is work that causes this redistribution of entropy. If equation (7) is the initial state of the system, and brute force (work) is used, the next state looks like this:
\[ H = \log_2(2^n-1) + \log_2(2^n) - \log_2(2^n-1) + \epsilon \hspace{.5 cm}(\epsilon\geq 0) \hspace{1 cm} (10) \]If $2^n-n^k$ steps of work are performed, the search space shrinks to $n^k$ and can be searched in polynomial time (see equation (9)). The $P=NP?$ question could be reframed as follows: \textit{Is there a way to reduce the search-space entropy without doing the astronomical amount of brute-force work required?}
The Value of Clues
To avoid violating the SLOT, let $A$ represent the active search-space entropy, which is initially $\log_2(2^n)$. Let $B$ represent the discard-space entropy corresponding to assignments that have either been bypassed (i.e., not assigned) or assigned but failed to satisfy $\phi$. Initially, $B = 0$. The initial entropy equation is expressed as follows:
\[ H = \log_2(2^n) + 0 \hspace{.5 cm}(A= \log_2(2^n);\hspace{.1 cm}B=0) \hspace{1 cm} (11) \]To solve an NP-complete instance $\phi$ in polynomial time, a Turing machine $M$ requires an algorithm $\alpha$ capable of deciding which assignments should be tested ($A$), and which can be safely bypassed ($B$). Without clues, there is no deterministic basis for this partition; there is only a random or arbitrary basis that may cause the solution(s) to be missed. Clues encompass, but are not limited to, patterns, extrinsic or intrinsic evidence, and any helpful structural information. Thus, the framework for $\alpha$ can be structured as follows:
1. Evaluate Clues: Execute conditional statements that evaluate available clues to determine the largest number of potential assignments that can be safely bypassed, making entropy $A$ smaller and entropy $B$ larger.
2. Search Remainder: Perform a brute-force search over the remaining potential assignments. Each tested assignment reduces entropy A and increases entropy B.
3. Iterate: Repeat steps 1 and 2 until $A = log_2(\gamma)$; where $\gamma$ is the smallest number that includes the satisfying assignment(s).
To demonstrate this mechanism, suppose $M$ is given a maximal clue: the exact solution to $\phi$. The entropy equation is as follows:
\[ H = \log_2(1) + \log_2(2^n) - \log_2(1) + \epsilon \hspace{.5 cm}(A = \log(1); B = \log_2(2^n) - \log_2(1); \hspace{.1 cm}\epsilon \geq 0) \hspace{1 cm} (12) \]$M$ executes step 1 by evaluating the clue and isolating the solution, i.e., reducing $A$ while increasing $B$. During step 2, $M$ tests the remaining single assignment. The total runtime is $O(1)$, bypassing step 3 entirely.
Now, suppose $M$ is provided with minor clues. The entropy equation can be modeled in the following manner:
\[ H = \log_2(n^k) + \log_2(2^n) - \log_2(n^k) + \epsilon \hspace{.5 cm}(A = \log(n^k); B = \log_2(2^n) - \log_2(n^k); \hspace{.1 cm}\epsilon \geq 0) \hspace{1 cm} (13) \]where $M$ can solve the instance in polynomial time using the framework above. However, if $M$ has no clues to leverage, step 1 is bypassed, and only steps 2 and 3 are executed. The entropy equation reverts to:
\[ H = \log_2(2^n) \hspace{1 cm} (14) \]Absent any clues, $M$ cannot solve $\phi$ deterministically in polynomial time. A groundless reduction in search space size would violate the SLOT:
\[ H \neq \log_2(n^k) \hspace{1 cm} (15) \]Conclusion
Based on the fundamental definition of a mathematical function, we conclude that a general, deterministic inverse function is untenable. Based on the SLOT and the necessity of clues to deterministically partition a combinatorial search space, we conclude that a universal polynomial-time algorithm for unguided instances cannot exist. Therefore, we state that:
\[ P \neq NP. \hspace{1 cm} (16) \]References
1. Cook, Stephen. \textit{The P versus NP Problem}. Clay Mathematics Institute.
2. Cook, Stephen. 1971. \textit{The complexity of theorem proving procedures}. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. doi:10.1145/800157.805047. ISBN 9781450374644. S2CID 7573663.
3. Herrmann, Paul Peter. 1973. \textit{On the Reducibility Among Combinatorial Problems}. Massachusetts Institute of Technology.
4. Karp, Richard M. 1972. \textit{Reducibility Among Combinatorial Problems}. In Miller, Raymond E.; Thatcher, James W. (eds.). \textit{Complexity of Computer Computations}. New York: Plenum. pp. 85–103. ISBN 0-306-30707-3.
© 2026 G.M. Jackson
