A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
Pith reviewed 2026-05-18 05:04 UTC · model grok-4.3
The pith
Every MAX-k-SAT instance contains exponentially many assignments that nearly match the optimum number of satisfied clauses.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that for every instance of MAX-k-SAT, and more generally every instance of MAXCSP, the number of assignments satisfying at least a (1-ε) fraction of the optimum number of clauses is exponential in the number of variables. The authors establish this existence by a direct counting argument that holds for arbitrary clause structures and requires no density or interaction restrictions on the input.
What carries the argument
A counting argument showing that exponentially many assignments are near-optimal in any MAX-k-SAT or MAXCSP instance.
If this is right
- Repeated uniform random sampling yields a simple (1-ε)-approximation algorithm for MAX-k-SAT.
- The algorithm requires only polynomial space and runs faster than previous polynomial-space methods for the same guarantee.
- The same exponential abundance of good assignments holds for the general MAXCSP setting.
- No derandomization or advanced sampling techniques are required to achieve the stated running-time bound.
Where Pith is reading between the lines
- The abundance result may explain why simple local-search heuristics often locate good solutions quickly on typical MAX-k-SAT instances.
- The same counting approach could be tested on other exponential-time approximation problems in constraint satisfaction to see whether similar abundance holds.
- Future algorithms might try to construct one of the many good assignments explicitly rather than sampling for it.
Load-bearing premise
The counting argument establishing an exponential supply of near-optimal assignments works for every possible MAX-k-SAT instance without any restrictions on clause density or variable interactions.
What would settle it
An explicit MAX-k-SAT formula in which the number of assignments satisfying more than (1-ε) times the optimum fraction of clauses is smaller than 2^{c n} for some constant c less than 1 would falsify the claim.
read the original abstract
We present an extremely simple polynomial-space exponential-time $(1-\varepsilon)$-approximation algorithm for MAX-k-SAT that is (slightly) faster than the previous known polynomial-space $(1-\varepsilon)$-approximation algorithms by Hirsch (Discrete Applied Mathematics, 2003) and Escoffier, Paschos and Tourniaire (Theoretical Computer Science, 2014). Our algorithm repeatedly samples an assignment uniformly at random until finding an assignment that satisfies a large enough fraction of clauses. Surprisingly, we can show the efficiency of this simpler approach by proving that in any instance of MAX-k-SAT (or more generally any instance of MAXCSP), an exponential number of assignments satisfy a fraction of clauses close to the optimal value.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper presents a simple polynomial-space exponential-time (1-ε)-approximation algorithm for MAX-k-SAT. The algorithm works by repeatedly sampling assignments uniformly at random until one is found that satisfies a fraction of clauses close to the optimum. The key supporting claim is a probabilistic existence argument showing that every MAX-k-SAT instance (and, more generally, every MAXCSP instance) contains an exponential number of such near-optimal assignments, which justifies that the expected number of trials remains 2^{o(n)}.
Significance. If the exponential-count claim holds for fixed-arity MAX-k-SAT, the algorithm supplies a markedly simpler alternative to the prior polynomial-space (1-ε)-approximations of Hirsch (2003) and Escoffier-Paschos-Tourniaire (2014) while improving the running-time exponent by a small constant factor. The direct probabilistic argument avoids intricate reductions and supplies a clean, falsifiable statement about the size of the near-optimal solution set.
major comments (2)
- [Abstract] Abstract and §1: The manuscript asserts that the exponential-count result holds for 'any instance of MAXCSP'. This statement is incorrect. A single n-ary constraint satisfied by exactly one assignment (e.g., the all-true vector) yields only one assignment meeting the (1-ε)·OPT threshold for ε<1, so the measure is 2^{-n}, not exponential. The claimed running-time bound therefore fails for unrestricted-arity MAXCSP; the proof must be restricted to fixed k or the generality claim removed.
- [§3] The central running-time analysis (presumably §3 or §4) relies on the exponential-count lemma to bound the expected number of samples. Because the lemma is stated for arbitrary MAXCSP, the analysis does not establish the claimed 2^{o(n)} bound once the counterexample is admitted; a corrected statement limited to MAX-k-SAT is required.
minor comments (2)
- [Abstract] The abstract should explicitly state the dependence of the running-time exponent on k and ε rather than leaving it implicit.
- [§2] Clarify whether the sampling procedure is with or without replacement and how the stopping threshold is computed from the unknown OPT.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for identifying the overstatement in our generality claim. We agree that the exponential-count result does not hold for MAXCSP with unrestricted arity, and we will revise the manuscript to restrict all statements, the lemma, and the running-time analysis to MAX-k-SAT and, more generally, to MAXCSP with fixed arity. This resolves both major comments without affecting the main result for MAX-k-SAT.
read point-by-point responses
-
Referee: [Abstract] Abstract and §1: The manuscript asserts that the exponential-count result holds for 'any instance of MAXCSP'. This statement is incorrect. A single n-ary constraint satisfied by exactly one assignment (e.g., the all-true vector) yields only one assignment meeting the (1-ε)·OPT threshold for ε<1, so the measure is 2^{-n}, not exponential. The claimed running-time bound therefore fails for unrestricted-arity MAXCSP; the proof must be restricted to fixed k or the generality claim removed.
Authors: We agree that the claim as written for arbitrary-arity MAXCSP is incorrect, and the counterexample is valid. The probabilistic argument establishing an exponential number of near-optimal assignments requires bounded arity (to ensure that the fraction of satisfying assignments for each constraint is bounded away from zero in a way that permits a union-bound or sampling argument over the variables). We will revise the abstract, §1, the lemma statement, and all subsequent references to replace 'any instance of MAXCSP' with 'any instance of MAXCSP with fixed arity k' (or equivalently, restrict the generality claim to MAX-k-SAT). The running-time bound 2^{o(n)} will be stated only under this restriction. revision: yes
-
Referee: [§3] The central running-time analysis (presumably §3 or §4) relies on the exponential-count lemma to bound the expected number of samples. Because the lemma is stated for arbitrary MAXCSP, the analysis does not establish the claimed 2^{o(n)} bound once the counterexample is admitted; a corrected statement limited to MAX-k-SAT is required.
Authors: We agree that the analysis in §3 inherits the same overstatement. Once the lemma is corrected to apply only to fixed-arity instances, the expectation calculation (showing that the success probability per trial is 2^{-o(n)}) goes through unchanged for MAX-k-SAT. We will add an explicit sentence in §3 stating that the analysis assumes fixed arity and will update the theorem statement to reflect the corrected scope. revision: yes
Circularity Check
Probabilistic existence proof is self-contained with no definitional or citation reduction
full rationale
The paper derives its running-time bound from a direct probabilistic counting argument establishing that every MAX-k-SAT (and claimed MAXCSP) instance possesses an exponential number of near-optimal assignments. This step relies on standard first-principles probability rather than any fitted parameter renamed as a prediction, self-citation chain, or imported uniqueness theorem. No equation reduces to an earlier definition by construction, and the central claim does not depend on prior work by the same authors as its sole justification. The derivation therefore stands independently of the input data or external fitted results.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard concentration or counting bounds from probability theory suffice to show that the fraction of near-optimal assignments is at least 2^{-O(n)}.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.