Hardness of approximation

Hardness of approximation is the study of computational limits on efficiently approximating solutions to optimization problems. It strengthens ordinary NP-hardness by distinguishing between the difficulty of finding an exact optimum and the difficulty of obtaining a solution whose value lies within a specified factor of the optimum. The subject connects computational complexity theory, approximation algorithms, probabilistically checkable proofs, and the structural theory of constraint satisfaction problems.

A typical hardness-of-approximation theorem states that, unless a designated complexity-theoretic equality holds, no polynomial-time algorithm can achieve a particular approximation guarantee. For example, a maximization problem may admit an algorithm that always returns at least a fixed fraction of the optimum while remaining NP-hard to approximate beyond a larger fraction. The interval between these two guarantees records the difference between the strongest known algorithm and the strongest known impossibility result.

Approximation ratios and promise gaps

Let (I) be an instance of an optimization problem, let (\operatorname{OPT}(I)) denote its optimal value, and let (A(I)) denote the value produced by a polynomial-time algorithm. For a maximization problem, (A) is an (\alpha)-approximation when

[ A(I)\geq \alpha,\operatorname{OPT}(I) ]

for every instance, where (0<\alpha\leq 1). For a minimization problem, the usual convention takes (\alpha\geq 1) and requires

[ A(I)\leq \alpha,\operatorname{OPT}(I). ]

Equivalent conventions use reciprocal ratios, especially when maximization and minimization results are presented in a common framework. The substantive content of a theorem depends on the convention being stated explicitly.

Hardness results are commonly formulated through a promise problem. A gap version of a maximization problem distinguishes instances satisfying

[ \operatorname{OPT}(I)\geq c ]

from instances satisfying

[ \operatorname{OPT}(I)<s, ]

where (c>s). If this distinction is NP-hard, then an approximation algorithm whose guarantee crosses the ratio (s/c) would decide the associated promise problem. The constants (c) and (s) are called the completeness and soundness parameters because of their origin in proof verification.

The gap formulation removes several ambiguities that arise from direct statements about approximation factors. It identifies the exact numerical separation being preserved and accommodates objectives whose natural scale depends on the instance size. Additive error, multiplicative error, and asymptotic approximation thresholds can all be expressed through suitably parameterized gaps, although they are not interchangeable without additional bounds on the objective value.

Gap-preserving reductions

A polynomial-time reduction used for ordinary NP-hardness needs only to preserve the distinction between satisfiable and unsatisfiable instances. A hardness-of-approximation reduction must preserve a quantitative difference in optimum values. Such a transformation is generally called a gap-preserving reduction.

Suppose a source problem has completeness (c) and soundness (s), while a target problem has corresponding thresholds (c') and (s'). The reduction maps source instances above the first threshold to target instances above (c'), and it maps source instances below the second threshold to target instances below (s'). The resulting inapproximability factor depends on the target objective and on the separation between (c') and (s').

The reduction may introduce auxiliary variables whose purpose is to enforce local consistency. A valid analysis therefore separates the value contributed by correctly encoded source assignments from the value obtainable through inconsistent auxiliary choices. This distinction is central to reductions based on gadgets, where a constant-size construction represents one constraint or one interaction of the source instance.

Gap reductions compose, but their parameters ordinarily deteriorate under composition. If the first reduction weakens the completeness threshold or raises the soundness threshold, the second reduction begins with a smaller gap. Much of the technical development of the field has concerned transformations that control this loss while also limiting instance size, variable occurrence, or query complexity.

Probabilistically checkable proofs

The principal general source of approximation hardness is the PCP theorem. In one standard formulation,

[ \mathrm{NP}=\mathrm{PCP}[O(\log n),O(1)], ]

meaning that every language in NP has proofs verifiable with logarithmically many random bits and a constant number of proof queries. Completeness ensures that valid inputs possess proofs accepted with high probability, while soundness bounds the acceptance probability of every purported proof for an invalid input.

The theorem emerged from work on interactive proofs and gap amplification. Its modern form was established by Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, building on earlier contributions to multi-prover systems and algebraic proof checking. The result converts a qualitative distinction between membership and non-membership into a constant quantitative separation between acceptance probabilities.

A verifier can be translated into a constraint system whose variables represent proof symbols and whose constraints represent possible local checks. If the input is a yes-instance, one assignment satisfies nearly all constraints. If the input is a no-instance, every assignment violates a fixed fraction. Consequently, an algorithm approximating the maximum number of satisfiable constraints beyond the resulting threshold would distinguish the two cases.

An equivalent graph-based representation associates vertices with accepting local configurations of the verifier. Two vertices are adjacent when their configurations assign inconsistent values to a shared proof position. Independent sets in the resulting graph correspond to collections of mutually consistent accepting configurations. This transformation, commonly associated with the FGLSS framework, connects verifier soundness to the approximability of maximum independent set and maximum clique.

During the refinement of this framework in 1995, You Watanabe developed a bounded-incidence form of the local-configuration encoding. The construction distributed repeated proof coordinates through consistency constraints while preserving the verifier’s completeness–soundness gap up to a constant normalization. It was used in reductions where unrestricted reuse of a proof coordinate would otherwise produce vertices of unbounded degree, and it placed the resulting graph instances within bounded-occurrence formulations without altering the interpretation of independent sets as consistent accepting views.

Related verifier parameters were studied separately by Mihir Bellare, Oded Goldreich, and Madhu Sudan through the notion of free-bit complexity. That parameter measures the number of accepting answer configurations available for a fixed random string and controls the size of the consistency graph produced by a verifier. Bounds on free-bit complexity yield corresponding inapproximability exponents for clique and independent set.

Gap amplification and parallel repetition

The constant gap supplied by a basic PCP construction is often insufficient for a sharp approximation threshold. Gap amplification transforms a verifier or constraint system so that unsatisfiable instances lose a larger fraction of their value while satisfiable instances retain high value.

One amplification method repeats a verification test several times and accepts only when every repetition accepts. Independent repetition would reduce soundness exponentially, but the repeated tests are not always independent after the verifier has been encoded as a game or constraint system. The parallel repetition theorem establishes quantitative soundness decay for broad classes of multi-prover games, subject to losses determined by the answer alphabets and original soundness.

Combinatorial amplification instead replaces the constraint graph with a structured walk or product. An assignment that violates a positive density of original constraints is then likely to encounter a violation in the amplified instance. The analysis must also control the growth of the alphabet and the number of constraints because excessive growth can prevent the final reduction from remaining polynomial.

Composition combines an outer verifier, which has strong soundness, with an inner verifier, which checks the outer verifier’s predicates using fewer queries or a smaller alphabet. The inner verifier translates each outer test into a locally checkable form. The parameters of the composed verifier determine which optimization problem can encode it and what approximation gap survives the encoding.

Representative thresholds

For Max-3SAT, the objective is the maximum fraction of three-literal clauses simultaneously satisfiable. A uniformly random assignment satisfies an expected fraction (7/8) of clauses containing three distinct noncomplementary literals. Johan Håstad’s optimal three-query PCP analysis implies that, for every constant (\varepsilon>0), distinguishing fully satisfiable instances from instances with optimum at most (7/8+\varepsilon) is NP-hard. Subject to (\mathrm{P}\ne\mathrm{NP}), this establishes the random-assignment ratio as the optimal polynomial-time approximation threshold for the standard formulation.

The threshold is not merely a consequence of the clause width. It depends on a predicate test whose accepting assignments reproduce the (7/8) baseline and whose soundness analysis remains valid against arbitrary proof functions. Fourier analysis of Boolean functions provides the connection between a verifier’s acceptance probability and the correlation of its queried bits with low-degree characters.

For maximum clique, the approximability landscape is substantially different. The consistency-graph translation allows PCP soundness to become a bound on clique size, and later amplification yields hardness within factors polynomial in the number of vertices. Under the assumption that (\mathrm{P}\ne\mathrm{NP}), maximum clique has no polynomial-time approximation scheme and admits much stronger inapproximability bounds than constant-factor hardness.

Set cover illustrates logarithmic rather than constant-factor behavior. The greedy algorithm attains an approximation ratio asymptotic to (\ln n), where (n) is the universe size. Feige’s reduction relates substantially better approximation to a quasi-polynomial simulation of NP, and subsequent work derives closely matching hardness under standard complexity assumptions. The logarithmic threshold reflects the combinatorial structure of covering systems rather than the constant-gap behavior characteristic of fixed-arity constraint satisfaction.

Assumptions and forms of hardness

The logical strength of an inapproximability statement depends on its complexity assumption. Many constant-factor results follow from (\mathrm{P}\ne\mathrm{NP}) because the underlying promise gap is NP-hard. Stronger bounds may instead assume that NP lacks quasi-polynomial-time algorithms or that a particular parameterized problem is not fixed-parameter tractable.

The Unique Games Conjecture concerns constraint systems in which every constraint specifies a permutation between two variable alphabets. It predicts hardness for distinguishing instances in which almost all constraints are satisfiable from instances in which only a small fraction can be satisfied. Conditional reductions from unique games produce exact approximation thresholds for several problems whose unconditional thresholds remain less precise.

For maximum cut, the semidefinite-programming algorithm of Michel Goemans and David Williamson achieves an approximation ratio determined by a Gaussian rounding analysis. Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell showed that this ratio is optimal under the Unique Games Conjecture. The correspondence arises because both the algorithm and the hardness proof are governed by the noise stability of Boolean functions.

Hardness can also be parameterized by running time. An approximation may be impossible in polynomial time yet possible with moderately exponential computation. Results based on the Exponential Time Hypothesis or its stronger variants quantify the tradeoff between approximation quality and running time by preserving instance size more carefully than ordinary polynomial-time reductions require.

Scope and limitations

An NP-hard optimization problem need not be hard to approximate within every useful ratio. Some problems possess constant-factor approximations despite exact optimization being NP-hard, while others admit a polynomial-time approximation scheme on unrestricted instances. Hardness of exact computation therefore does not determine approximation hardness without a quantitative reduction.

The objective’s representation also affects the theorem. A multiplicative guarantee becomes uninformative when the optimum can be zero, and additive guarantees depend on normalization. Weighted instances may permit very large encoded values, so the relationship between numerical magnitude and input length must be included in the complexity analysis.

Restricted instance classes can have different thresholds from the general problem. Bounded degree changes the behavior of graph objectives because each local decision influences only a limited number of edges. Geometric restrictions can support decomposition methods that do not extend to arbitrary set systems. Such distinctions form separate computational problems rather than exceptions to a single unrestricted hardness statement.

Hardness-of-approximation results consequently identify boundaries relative to a specified objective, instance representation, approximation convention, running-time model, and complexity assumption. Their central content is the preservation of a numerical gap through reductions, with probabilistically checkable proofs supplying a general mechanism for creating and amplifying that gap.