SAT Requires Exhaustive Search

Ke Xu, Guangyan Zhou

TL;DR

This paper proposes a novel framework for proving computational hardness by drawing a direct parallel to Gödel’s Incompleteness Theorem. By constructing "self-referential" and "indistinguishable" instances of Constraint Satisfaction Problems (CSP), the authors prove that certain cases require exhaustive search to solve, effectively concluding that $P \neq NP$.

What Problem Does This Paper Address?

For decades, the $P$ vs $NP$ problem has remained the "holy grail" of computer science, yet progress on proving lower bounds has been stalled by significant theoretical barriers, such as the relativization barrier and the natural proof barrier.

The authors argue that the field has been stuck because it relies too heavily on Turing’s framework of computability, which they view as a physical assumption about machines. Instead, they suggest that computational hardness is a mathematical limit of reasoning itself. The core challenge they tackle is the gap between syntax (the rules an algorithm follows) and semantics (the actual truth or satisfiability of a problem). They aim to show that for some problems, no amount of "syntactic" reasoning (shortcuts) can replace "semantic" verification (exhaustive search).

Methods

The authors move away from abstract complexity classes and focus on a constructive approach. Their primary tools include:

  • Model RB: A random CSP model where the domain size ($d$) grows with the number of variables ($n$). This model is known for having sharp phase transitions from "satisfiable" to "unsatisfiable."
  • Symmetry Mapping: The authors define a transformation that can flip a CSP instance from being satisfiable (with exactly one solution) to unsatisfiable (failing on only one constraint) while keeping the subproblems identical.
  • Diagonalization and Self-Reference: Inspired by Gödel, they construct "Most Indistinguishable Examples." These are pairs of instances that look identical to any algorithm that doesn't perform a full search.
  • Formal System Analogy: They treat algorithms as finite formal systems. Using Lemma 3.1, they demonstrate that if an algorithm runs in sub-exponential time, it effectively tries to solve the problem by looking at a limited number of subproblems. They then use their constructed examples to show that these subproblems are insufficient to determine the global truth.

Datasets

The paper does not use traditional training datasets like ImageNet. Instead, it utilizes:

  • Model RB Instances: Specifically, random CSP instances generated with parameters that place them at the "phase transition" point where problems are hardest.
  • frb100-40: A specific benchmark instance of Model RB (100 variables, domain size 40) that has remained unsolved since 2005, serving as a real-world example of the "extreme hardness" they describe.

Key Insights and Ideas

  • Construction is All You Need: The authors argue that we don't need to prove things about all algorithms for all problems. By constructing specific, extremely hard instances, they can prove that no efficient algorithm can solve them.
  • The Gödel Connection: Just as Gödel showed that some mathematical truths cannot be reached via formal rules (syntax), this paper argues that the satisfiability of certain CSPs cannot be reached via algorithmic shortcuts.
  • Bypassing Barriers: They claim to circumvent the relativization barrier because their self-reference method is applied to constructed examples rather than the entire class of NP problems. They bypass the natural proof barrier by showing that extreme hardness is "easy to understand" once you have the right construction.
  • Syntax vs. Semantics: The fundamental difference between a "fast" algorithm and exhaustive search is that the former relies on syntactic patterns, while the latter is a brute-force semantic check. The paper proves that for their constructed instances, syntax is provably insufficient.

Key Results

  • Theorem 3.2: The authors prove that Model RB cannot be solved in $O(d^{cn})$ time for any constant $c < 1$. This means exhaustive search is mandatory.
  • Corollary 3.3: By encoding CSP into SAT, they show that SAT with $N$ Boolean variables cannot be solved in $O(2^{cN})$ time for $c < 1$.
  • P $\neq$ NP: Since they have proven that a problem in $NP$ (SAT/CSP) requires exponential time (exhaustive search), they conclude that $P \neq NP$.
  • Hardness is "Easy": They demonstrate that while proving lower bounds for 3-SAT is hard (because many shortcuts exist), proving them for "extremely hard" examples with long clauses or large domains is actually more straightforward.

Limitations and Future Work

  • Mathematical Assumptions: The proof relies on a specific mathematical assumption about the nature of reasoning (specifically, that solving a problem involves dividing it into subproblems). While the authors argue this is consistent with reality, it is a foundational premise that others might scrutinize.
  • Scope of SAT: The results are most directly applicable to SAT with "long clauses" (derived from large-domain CSPs). The authors note that separating SAT with long clauses from 3-SAT is easier than the traditional 3-SAT vs 2-SAT separation, leaving room for more granular work on standard $k$-SAT benchmarks.
  • Physical vs. Mathematical: The paper draws a sharp line between Turing's "physical" limits and their "mathematical" limits. Exploring how these two perspectives reconcile in quantum computing or other non-classical models could be a future direction.

Summary updated

Abstract

In this paper, by constructing extremely hard examples of CSP (with large domains) and SAT (with long clauses), we prove that such examples cannot be solved without exhaustive search, which is stronger than P $\neq$ NP. This constructive approach for proving impossibility results is very different (and missing) from those currently used in computational complexity theory, but is similar to that used by Kurt Gödel in proving his famous logical impossibility results. Just as shown by Gödel's results that proving formal unprovability is feasible in mathematics, the results of this paper show that proving computational hardness is not hard in mathematics. Specifically, proving lower bounds for many problems, such as 3-SAT, can be challenging because these problems have various effective strategies available for avoiding exhaustive search. However, in cases of extremely hard examples, exhaustive search may be the only viable option, and proving its necessity becomes more straightforward. Consequently, it makes the separation between SAT (with long clauses) and 3-SAT much easier than that between 3-SAT and 2-SAT. Finally, the main results of this paper demonstrate that the fundamental difference between the syntax and the semantics revealed by Gödel's results also exists in CSP and SAT.
BibTeX
@misc{xu2023sat,
  author = {Ke Xu and Guangyan Zhou},
  title = {{SAT Requires Exhaustive Search}},
  year = {2023},
  eprint = {2302.09512},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.09512},
}
Figure