On Super Strong ETH

Nikhil Vyas, R. Ryan WilliamsJAIR 2021 · DOI

TL;DR

This paper challenges a long-standing hypothesis about the inherent difficulty of solving Boolean satisfiability problems (k-SAT). The authors demonstrate that for certain types of k-SAT instances, specifically random and "planted" ones, it's possible to find solutions significantly faster than previously thought possible, effectively refuting the "Super-Strong ETH" for these cases.

What Problem Does This Paper Address?

The field of computational complexity has long grappled with the problem of determining whether a given Boolean formula is satisfiable (k-SAT). While k-SAT is NP-complete, meaning no known polynomial-time algorithm exists for all instances, researchers have been trying to find faster algorithms that might beat the exponential lower bounds. The "Exponential Time Hypothesis" (ETH) and its stronger variants (SETH, Super-SETH) posit that there are fundamental limits to how fast we can solve k-SAT, even with super-polynomial time algorithms. Specifically, the Super-Strong ETH suggests that we cannot achieve a runtime of $2^{n(1 - f(k)/k)}$ for any unbounded function $f(k)$, implying that the $1/k$ factor in the exponent's savings is essentially optimal. This paper investigates whether this theoretical barrier holds for average-case instances, particularly those found in practice or generated near a "critical threshold" where satisfiability becomes highly sensitive to parameters.

Methods

The core of this paper lies in leveraging and adapting existing algorithms, primarily the PPZ algorithm (Paturi, Pudlák, and Zane), which is known for its effectiveness in solving k-SAT. The authors' key contributions are:

  • Refuting Super-Strong ETH for Random/Planted k-SAT: They show that the PPZ algorithm, when applied to random or "planted" k-SAT instances (where a hidden solution is embedded), achieves a runtime of $2^{n(1 - \Omega(\log k)/k)}$. This is faster than the Super-Strong ETH would allow for these specific instance types.
  • Reduction from k-SAT to Unique k-SAT: They establish a strong equivalence between the complexity of general k-SAT and "Unique k-SAT" (where there's at most one satisfying assignment). This means that if we could solve Unique k-SAT significantly faster, we could also solve general k-SAT faster, simplifying the search for faster algorithms by focusing on the unique case.
  • Analysis of Unit Propagation: A crucial part of their analysis involves understanding how often "unit propagation" (a simple simplification rule in SAT solvers) can be effectively applied to random instances. They show that for random instances, unit propagation can assign a surprisingly large number of variables, leading to significant speedups.

Datasets

Not discussed in the paper. The paper focuses on theoretical distributions of k-SAT instances:

  • R(n,k,m): Standard random k-SAT distribution.
  • R+(n,k,m): Random k-SAT conditioned on satisfiability.
  • P(n,k,m,σ): Planted k-SAT distribution with a hidden solution σ.

Key Insights and Ideas

  • Average-Case vs. Worst-Case: The paper strongly suggests that average-case instances of k-SAT (especially random ones near the threshold) are significantly easier to solve than worst-case instances, contradicting the idea that theoretical worst-case hardness directly translates to practical difficulty for all instance types.
  • The Power of Simple Heuristics: The fact that a relatively simple algorithm like PPZ, relying on unit propagation and random choices, can break the Super-Strong ETH for random instances highlights the effectiveness of basic SAT solving techniques when applied to structured or random inputs.
  • Equivalence of k-SAT Variants: The tight correlation shown between the complexity of general k-SAT and Unique k-SAT is a significant theoretical result. It implies that progress in solving one directly translates to progress in the other, potentially simplifying research efforts.

Key Results

  • Random/Planted k-SAT: An algorithm is presented that finds a satisfying assignment for random and planted k-SAT instances in $2^{n(1 - \Omega(\log k)/k)}$ time with high probability, refuting the Super-Strong ETH for these cases.
  • Unique k-SAT Equivalence: A reduction shows that if Unique k-SAT can be solved in $2^{n(1 - f(k)/k)}$ time, then k-SAT can be solved in $2^{n(1 - f(k)/k + O(\log f(k)/k))}$ time. This establishes a near-equivalence for Super-SETH.

Limitations and Future Work

  • Worst-Case Hardness: The paper does not refute the Super-Strong ETH for worst-case k-SAT instances. The algorithms presented are for specific, structured distributions.
  • Feige's Hypothesis: The authors mention that their work does not resolve Feige's Hypothesis regarding efficient refutations for random k-SAT near the threshold, leaving this as an intriguing open problem.
  • Further Improvements: The paper hints at potential further improvements for random k-SAT instances when the clause density ($m/n$) is further away from the threshold, suggesting that even faster algorithms might exist in those regimes. The authors also note that subsequent work has presented algorithms with even faster running times for random k-SAT.

Summary updated

BibTeX
@article{vyas2021super,
  author = {Nikhil Vyas and R. Ryan Williams},
  title = {{On Super Strong ETH}},
  journal = {J. Artif. Intell. Res.},
  year = {2021},
  doi = {10.1613/jair.1.11859},
}
Figure