If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances

Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma

Abstract

This paper establishes a landmark result in computational complexity: the first-ever worst-case to average-case reduction for NP-complete problems. It proves that if SAT is hard in the worst case, then for any efficient algorithm, we can efficiently generate a distribution of inputs that causes that specific algorithm to fail. This effectively bridges a long-standing gap in our understanding of problem hardness.

Introduction

In computational complexity, we typically distinguish between worst-case hardness—the existence of at least one difficult input—and average-case hardness, where a problem is difficult for most inputs chosen from a specific distribution. While the former is the basis for the $P \neq NP$ conjecture, the latter is essential for practical applications like cryptography. For decades, it remained unproven whether worst-case hardness for NP-complete problems like SAT implied average-case hardness. This paper addresses this by showing that if an algorithm claims to solve SAT efficiently, we can "call its bluff" by efficiently finding instances where it fails.

Methodology: The Non-Black-Box Reduction

The authors introduce a "non-black-box" reduction. Unlike standard reductions that treat an algorithm as an opaque "magic box," this method utilizes the internal description (the code) of the candidate algorithm to identify its weaknesses.

The core of the approach is a Search Algorithm (SSAT) built upon a candidate SAT-solver (BSAT). The process relies on two primary pillars:

  1. Self-Reducibility: If an algorithm can decide if a formula is satisfiable, it can be used to find the actual assignment by fixing variables one by one.
  2. The Refutation Lemma: The authors construct a logical statement $\phi_n$ that asserts: "There exists a formula of length $n$ where the current algorithm (BSAT) provides an incorrect answer."

Because $\phi_n$ is itself an NP statement, it can be converted into a SAT formula and fed back into the algorithm. If the algorithm claims there are no hard instances (answering "No"), $\phi_n$ itself becomes the hard instance. If it answers "Yes," the search properties allow the authors to extract the specific formula on which the algorithm fails.

Key Results and Theoretical Implications

The paper focuses on "Pseudo-classes" (e.g., $PseudoBPP$), where hardness is defined relative to a specific algorithm.

Theorem 1.5: Algorithm-Specific Hardness

If $NP \neq P$, then for every deterministic polynomial-time algorithm, there exists a samplable distribution where it fails at least 1/6th of the time. For probabilistic algorithms ($BPP$), a similar result holds with a failure rate of at least 3/100.

Theorem 1.6: Fixed Distribution Hardness

The authors demonstrate the existence of a fixed distribution—one that does not change based on the algorithm—that is samplable in quasi-polynomial time ($n^{\log n}$). This distribution is hard for all efficient probabilistic algorithms, assuming NP is hard in the worst case.

The Three-Formula Lemma

A particularly striking result is the proof that given any efficient algorithm failing on SAT, one can efficiently generate a set of at most three formulas such that the algorithm is guaranteed to fail on at least one of them.

Conclusion and Future Directions

This work effectively eliminates the possibility of "Super-Heuristica," one of Impagliazzo’s theoretical worlds where NP is hard in the worst case but easy for every efficiently samplable distribution.

However, limitations remain. The results provide "mild" hardness rather than the "strong" hardness required for cryptography (where an algorithm performs no better than a random guess). Furthermore, the fixed distribution requires quasi-polynomial time to sample, whereas cryptographic applications require polynomial time. Future research will likely focus on optimizing these constants and exploring the path toward proving the existence of One-Way Functions based on worst-case NP-hardness.

Summary updated

Abstract

We prove that if NP $${\nsubseteq}$$ BPP, i.e., if SAT is worst-case hard, then for every probabilistic polynomial-time algorithm trying to decide SAT, there exists some polynomially samplable distribution that is hard for it. That is, the algorithm often errs on inputs from this distribution. This is the first worst-case to average-case reduction for NP of any kind. We stress however, that this does not mean that there exists one fixed samplable distribution that is hard for all probabilistic polynomial-time algorithms, which is a pre-requisite assumption needed for one-way functions and cryptography (even if not a sufficient assumption). Nevertheless, we do show that there is a fixed distribution on instances of NP-complete languages, that is samplable in quasi-polynomial time and is hard for all probabilistic polynomial-time algorithms (unless NP is easy in the worst case).Our results are based on the following lemma that may be of independent interest: Given the description of an efficient (probabilistic) algorithm that fails to solve SAT in the worst case, we can efficiently generate at most three Boolean formulae (of increasing lengths) such that the algorithm errs on at least one of them.
BibTeX
@article{gutfreund2007if,
  author = {Dan Gutfreund and Ronen Shaltiel and Amnon Ta-Shma},
  title = {{If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances}},
  journal = {Comput. Complex.},
  year = {2007},
  doi = {10.1007/s00037-007-0235-8},
}
Figure