Editing Clique problem (section)

===Hardness of approximation===
[[File:Cube-face-intersection-graph.svg|thumb|A graph of compatibility relations among 2-bit samples of 3-bit proof strings. Each maximal clique (triangle) in this graph represents all ways of sampling a single 3-bit string. The proof of inapproximability of the clique problem involves [[induced subgraph]]s of analogously defined graphs for larger numbers of bits.]]
Weak results hinting that the clique problem might be hard to approximate have been known for a long time. {{harvtxt|Garey|Johnson|1978}} observed that, because the clique number takes on small integer values and is NP-hard to compute, it cannot have a [[Polynomial-time approximation scheme|fully polynomial-time approximation scheme]], unless P&nbsp;=&nbsp;NP. If too accurate an approximation were available, rounding its value to an integer would give the exact clique number. However, little more was known until the early 1990s, when several authors began to make connections between the approximation of maximum cliques and [[probabilistically checkable proof]]s. They used these connections to prove [[hardness of approximation]] results for the maximum clique problem.<ref>{{harvtxt|Feige|Goldwasser|Lovász|Safra|1991}}; {{harvtxt|Arora|Safra|1998}}; {{harvtxt|Arora|Lund|Motwani|Sudan|1998}}.</ref>
After many improvements to these results it is now known that, for every [[real number]] {{math|''ε''&nbsp;>&nbsp;0}}, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than {{math|{{italics correction|''O''}}(''n''<sup>1&nbsp;&minus;&nbsp;''ε''</sup>)}}, unless [[P versus NP problem|P = NP]].<ref>{{harvtxt|Håstad|1999}} showed inapproximability for this ratio using a stronger complexity theoretic assumption, the inequality of [[NP (complexity)|NP]] and [[ZPP (complexity)|ZPP]]. {{harvtxt|Khot|2001}} described more precisely the inapproximability ratio, but with an even stronger assumption. {{harvtxt|Zuckerman|2006}} [[derandomization|derandomized]] the construction weakening its assumption to P&nbsp;≠&nbsp;NP.</ref>

The rough idea of these inapproximability results is to form a graph that represents a probabilistically checkable proof system for an NP-complete problem such as the Boolean satisfiability problem. In a probabilistically checkable proof system, a proof is represented as a sequence of bits. An instance of the satisfiability problem should have a valid proof if and only if it is satisfiable. The proof is checked by an algorithm that, after a polynomial-time computation on the input to the satisfiability problem, chooses to examine a small number of randomly chosen positions of the proof string. Depending on what values are found at that sample of bits, the checker will either accept or reject the proof, without looking at the rest of the bits. False negatives are not allowed: a valid proof must always be accepted. However, an invalid proof may sometimes mistakenly be accepted. For every invalid proof, the probability that the checker will accept it must be low.<ref name="inapprox-redux"/>

To transform a probabilistically checkable proof system of this type into a clique problem, one forms a graph with a vertex for each possible accepting run of the proof checker. That is, a vertex is defined by one of the possible random choices of sets of positions to examine, and by bit values for those positions that would cause the checker to accept the proof. It can be represented by a [[partial word]] with a 0 or 1 at each examined position and a [[wildcard character]] at each remaining position. Two vertices are adjacent, in this graph, if the corresponding two accepting runs see the same bit values at every position they both examine. Each (valid or invalid) proof string corresponds to a clique, the set of accepting runs that see that proof string, and all maximal cliques arise in this way. One of these cliques is large if and only if it corresponds to a proof string that many proof checkers accept. If the original satisfiability instance is satisfiable, it will have a valid proof string, one that is accepted by all runs of the checker, and this string will correspond to a large clique in the graph. However, if the original instance is not satisfiable, then all proof strings are invalid, each proof string has only a small number of checker runs that mistakenly accept it, and all cliques are small. Therefore, if one could distinguish in polynomial time between graphs that have large cliques and graphs in which all cliques are small, or if one could accurately approximate the clique problem, then applying this approximation to the graphs generated from satisfiability instances would allow satisfiable instances to be distinguished from unsatisfiable instances. However, this is not possible unless P&nbsp;=&nbsp;NP.<ref name="inapprox-redux">This reduction is originally due to {{harvtxt|Feige|Goldwasser|Lovász|Safra|1991}} and used in all subsequent inapproximability proofs; the proofs differ in the strengths and details of the probabilistically checkable proof systems that they rely on.</ref>
{{Clear}}