Source-linked AI summary
On Problems as Hard as CNFSAT
Marek Cygan, Holger Dell, Daniel Lokshtanov, Daniel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, Magnus Wahlstrom
TL;DR
The paper asks whether stalled improvements in exact exponential-time algorithms can be explained through a common complexity-theoretic assumption. It uses reductions and parity variants to establish SETH-equivalent lower bounds for several problems, while conditional results extend to Set Cover-related dynamic programs and leave the direct SETH-to-Set-Cover implication open.
Problem
The field lacks a complexity-theoretic framework for proving running-time lower bounds when exact exponential-time algorithms appear difficult to improve.
Method
The paper reduces bounded-width CNF-Sat to related search problems and studies parity versions to connect their exponential growth rates with SETH and ⊕-SETH.
Results
SETH is equivalent to O(2^εn) lower bounds for k-CNF-Sat, k-Hitting Set, k-Set Splitting, and k-NAE-Sat, while conditional Set Cover hardness yields tight bounds for four additional problems.
Takeaways & Limitations
The results show that the optimal exponential growth rates of several basic NP-hard problems are asymptotically interconnected, including problems solved by dynamic programming under the Set Cover assumption.
Takeaways & Limitations
The paper does not prove that SETH implies the required Set Cover hardness assumption and identifies this implication as an open problem.
Abstract
from arXiv · showhide
The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including Graph Coloring, Hamiltonian Path, Dominating Set and 3-CNF-Sat. In some instances, improving these algorithms further seems to be out of reach. The CNF-Sat problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2^n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-Sat that run in time o(2^n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every epsilon<1, there is a (large) integer k such that that k-CNF-Sat cannot be computed in time 2^{epsilon n}. In this paper, we show that, for every epsilon < 1, the problems Hitting Set, Set Splitting, and NAE-Sat cannot be computed in time O(2^{epsilon n}) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for Set Cover, and prove that, under this assumption, the fastest known algorithms for Steinter Tree, Connected Vertex Cover, Set Partitioning, and the pseudo-polynomial time algorithm for Subset Sum cannot be significantly improved. Finally, we justify our assumption about the hardness of Set Cover by showing that the parity of the number of set covers cannot be computed in time O(2^{epsilon n}) for any epsilon<1 unless SETH fails.
1 Introduction
The paper develops reductions that connect SETH to tight exponential-time lower bounds for several NP-complete problems, while conditional results extend to dynamic-programming and parity variants. It also identifies limitations around Set Cover and related reverse reductions.
- Motivation: The paper frames exponential-time lower bounds as a missing complexity-theoretic framework for explaining why improvements have stalled.Prior algorithms for problems such as Independent Set, Dominating Set, Graph Coloring, and Steiner Tree either repeatedly improved or appeared difficult to improve further.
- Main results: These problems share the naïve brute-force bound O(2^n), and their asymptotically equal optimal growth rates make improving CNF-Sat's growth rate below 2 comparably difficult under the reductions.The result is presented as a completeness statement under suitable reductions.
- Conditional extensions: Assuming a corresponding Set Cover hardness statement, Theorem 1.2 gives tight lower bounds for Steiner Tree, Connected Vertex Cover, Set Partitioning, and Subset Sum.The affected algorithms include the known dynamic-programming algorithms and the pseudo-polynomial Subset Sum algorithm.
- Limitations and open problems: The Set Cover assumption is not shown equivalent to SETH, and the paper leaves open whether SETH alone rules out 2^εn m^O(1)-time Set Cover algorithms.The authors explain that reverse reductions would likely require overcoming the non-triviality of the fastest known Steiner Tree algorithms.
- Parity results: Parity variants strengthen the connection: ⊕-SETH is equivalent to parity lower bounds for CNF-Sat, Hitting Set, and Set Cover, and rules out faster parity algorithms for Steiner Tree and Connected Vertex Cover.The paper also uses parity Set Cover hardness as evidence for the Set Cover assumption.
2 Preliminaries and Notation
The paper establishes notation for parameterized decision and parity problems across formulas, hypergraphs, graphs, and Subset Sum. It also defines the growth-rate measure and records a distinction between parity hardness at t=n and trivial decision instances.
- General notation: The notation k-Π bounds set or clause size by k, while c-Sparse-k-Π additionally bounds the number of sets or clauses by cn.These modifiers constrain the input promise without changing the problem’s goal.
- Parity problems: Parity problems ⊕Π ask whether the number of canonical solutions is odd, with size-at-most-t solutions counted when t is part of the input.For parity variants with t=n, the All modifier counts solutions of any size.
- Problem definitions: The basic problems span CNF satisfiability and NAE-Sat, hypergraph Hitting Set, Set Cover, Set Partitioning, Set Splitting, graph connectivity problems, and Subset Sum.CNF instances use n variables and m clauses; hypergraph instances use n vertices and m hyperedges.
- Problem definitions: Hitting Set selects at most t universe elements intersecting every hyperedge, whereas Set Cover selects at most t hyperedges whose union covers the universe.Set Partitioning requires the selected covering sets to be pairwise disjoint, and Set Splitting partitions the universe so every hyperedge meets both sides.
- Parity problems: For parity problems, hardness can remain nontrivial when t=n, although the corresponding decision setting is trivial.The All modifier makes this distinction explicit for problems such as Hitting Set.
3 On Improving Branching Algorithms
The section establishes reductions connecting CNF-Sat with Hitting Set and Set Splitting, showing that their exponential growth rates coincide and extending the connection to parity and circuit satisfiability.
- Reductions from CNF-Sat: σ(CNF-Sat/n) = σ(Hitting Set/n) = σ(Set Splitting/n), so faster algorithms for either search problem imply faster CNF-Sat algorithms.The reductions apply even to dense CNF-Sat instances.
- Sparse formulations: The sparsification framework transfers SETH to sparse Hitting Set and Set Splitting instances while preserving the relevant growth-rate comparison.The construction begins with Sparse-Hitting Set/n because its set count is linear in n.
- Correctness: Satisfying assignments correspond exactly to hitting sets of the constructed size, yielding a parsimonious reduction that also preserves parity counts.The forward and reverse directions use the block-size constraints and clause-specific sets.
- Counting and parity: The reductions remain polynomial-time without density or clause/set-size restrictions, and the hardness transfers to counting versions.The exact solution-count correspondence supports the parity reduction from CNF-⊕Sat to ⊕All Hitting Sets.
- Series-parallel circuits: For cn-size VSP circuits, depth reduction produces equivalent depth-3 unbounded-fan-in OR-AND-OR circuits, connecting circuit satisfiability to the same SETH-based landscape.The satisfiability problem has a 2^δn-time algorithm for δ < 1 if and only if SETH is false.
4 On Improving Dynamic Programming Based Algorithms
This section transfers parity hardness from Hitting Set to Set Cover and then to several dynamic-programming problems, using counting-preserving reductions and parameter transformations.
- Parity duality: Parity Hitting Set and parity Set Cover are equal for every set system, not merely after dualizing the instance.The proof routes both counts through independent sets in the incidence bipartite graph.
- Parameter symmetry: ⊕All Hitting Sets has a 1.99^n · poly(m + n) algorithm if and only if it has a 1.99^m · poly(m + n) algorithm.This exchanges the universe-size and family-size parameters.
- Hardness transfer: A 1.99^m · poly(m + n) algorithm for CNF-⊕Sat would imply a 1.99^n · poly(m + n) algorithm for the same problem, violating SETH.The implication follows by combining the parity reductions and parameter transformations.
- Graph reductions: Set Cover instances reduce to Steiner Tree and Connected Vertex Cover by using incidence graphs augmented with universal and pendant vertices.The constructions translate selected sets into Steiner trees or connected vertex covers with shifted size parameters.
- Set Cover parameter reduction: Grouping q sets into one larger set preserves Set Cover yes-instances while reducing the solution size to t′ ≤ α|U|.The transformed instance uses qk-Set Cover and is constructible in polynomial time for constant q.
- Subset Sum: Set Partitioning reduces to Subset Sum by encoding solution cardinality, total set size, and element coverage in separate bit fields.The target is reachable exactly when the sets form a partition of the universe using the chosen number of sets.
5 Summary and Open Problems
The paper finds strong interconnections among exponential-time complexities and derives tight conditional lower bounds, while leaving several important SETH-based questions open.
- Summary: The optimal growth rates of several basic problems are asymptotically equal, linking CNF-Sat, search problems, and dynamic-programming-based problems.The conclusions cover both brute-force growth rates and conditional lower bounds for dynamic-programming algorithms.
- Summary: Under SETH, tight growth-rate lower bounds follow for search problems whose known algorithms use naïve brute force.For dynamic-programming problems, the paper’s bounds rely on the conjectured Set Cover hardness assumption.
- Open Problems: Open problems include proving SETH-based lower bounds for Set Cover, Graph Coloring, circuit satisfiability, coloring counts, and concrete-base 3-CNF-Sat algorithms.The paper explicitly asks whether algorithms with exponent δ < 1 or concrete base c can be ruled out.