In this note, we are going to state the PCP theorem and its relation to the hardness of approximating some NP-hard problem.
PCP Theorem: the Interactive Proof View
Intuitively, a PCP (Probabilistically Checkable Proof) system is an interactive proof system where the verifier is given random bits and he is allowed to look into the proof in many locations. If the string is indeed in the language, then there exists a proof so that the verifier always accepts. However, if is not in the language, no prover can convince this verier with probability more than . The proof has to be short i.e., of size at most . This class of language is designated as PCP[r(n), q(n)].
Theorem A (PCP theorem). Every NP language has a highly efficient PCP verifier. In particular,
PCP Theorem: the Hardness of Approximation View
Given a Boolean formula with clauses on variables, let be the maximum fraction of satisfiable clauses, taken over all variables assignments. The MAX-3SAT problem asks you to find for a given . A -approximation to the MAX-3SAT problem, for , outputs a number .
It is easy to conceive a greedy -approximation algorithm for MAX-3SAT: for the th variable, choose the assignment that satisfies at least half of the remaining clauses, remove the satisfied clauses as well as the current variable from consideration, and repeat with the next variable. The celebrated algorithm of Goemans-Willamson (based on Semidefinite Programming) gives a -approximation.
Theorem B (Approximating MAX-3SAT is NP-hard). There exists a such that for every language in NP, there is an efficient mapping from the instances of the language to the instances of MAX-3SAT, so that if then , and otherwise .
The above theorem immediately implies that there is a constant such that if we have an efficient -approximation algorithm for MAX-3SAT, then it could be used to decide every NP language. In other words, P = NP.
The qCSP problem is a generalization of the 3SAT problem where -variable Boolean clauses are replaced by -variable Boolean functions called constraints. The -GAPCSP problem is a decision problem where given a Boolean formula , we have to decide whether is one, or strictly below .
Theorem C. There exists constants and such that the -GAP-CSP problem is NP-hard.
We claim that Theorem B is equivalent to the PCP Theorem (A), via Theorem C.
Theorem D. Theorems A, B, and C are equivalent.
Proof sketch: PCP implies GAP-CSP. Suppose NP equals . Here, given any NP language , the trick is to imagine a -CSP constraint as a Boolean predicate which is true if there exists a verifier which accepts . By the soundness and completeness of the PCP verifier, we have constructed a -GAPCSP instance. If one can decide this instance, he can also decide any NP language.
Proof sketch: GAP-CSP implies PCP. This is easy. Suppose you can decide an NP-hard -GAPCSP instance with clauses. You can construct a verifier as follows: randomly choose a constraint and query the literals in this clause. This verifier has completeness 1 and soundness . The soundness can be boosted down to with sequential repetition.
Proof sketch: Approximate MAX-3SAT implies GAP-3CSP. This is easy, just treat each 3-CNF clause as a 3CSP constraint.
Proof sketch: GAP-3CSP implies Approximate MAX-3SAT. The idea is to treat a constraint as an AND of -variable Boolean clauses, and then convert this formula into a 3-SAT formula.
INDSET is Fundamentally Harder than MIN-VERTEX-COVER
A Minimum Vertex Cover of a graph is a minimal set of vertices such that every other vertex is a neighbor to a member of this set. Computing the size of the minimum vertex cover of a graph is the MIN-VERTEX-COVER problem. A -approximation to MIN-VERTEX-COVER, for , outputs a set whose cardinality is at most a times larger than the size of the minimal cover.
Consider the following approximation algorithm for the minimum vertex cover in a graph : let be the empty set. Add an arbitrary edge in (that is, its endpoints), then delete its endpoints from as well as all edges adjacent to . Then repeat until no more edges can be included in . Since the edges in is a matching, any vertex cover must contain at least one vertex for every edge in ; hence . Hence this algorithm is a -approximation for MIN-VERTEX-COVER.
Recall that an Independent Set of a graph is a set of vertices that have no edges among themselves.
Fact (due to Tibor Gallai). The complement of the largest independent set in a graph is a minimum vertex cover.
Proof sketch: Fix the largest independent set in any connected graph . Each of the remaining vertices must have at least one edge with vertices in ; otherwise, would have been in . The size of any minimal vertex cover must be at least : Clearly, is a valid vertex cover, and if we exclude some , we have to compensate by picking at least one vertex from . If we use a different independent set , the size of cannot be any smaller than that of since is the largest independent set.
Lemma (Approximating MIN-VERTEX-COVER is hard for some ). There exists a constant such that computing a -approximation to the minimum vertex cover problem is NP-hard.
Proof sketch: Theorem B tells us that obtaining a -approximation to the MAX-3SAT problem is NP-hard. Given a 3-CNF formula , consider its conflict graph : every clause is associated with seven vertices, one for each candidate assignments to its literals. (One of the eight possible assignments for a clause can never satisfy the clause: namely, the assignment culminating in a Boolean OR of three zeros.) There is an edge in the graph (between vertices associated with different clauses) if and only if the two clauses conflict on the same variable. For example, the two clauses and conflict on the variable ; no assignment can satisfy them simultaneously. Suppose has vertices, in which case will have clauses.
The minimum vertex cover of has size , since the largest independent set in has size .
- Suppose . Then the size of the minimum vertex cover is at least since .
- Suppose . A approximation to the minimum vertex cover would give us a vertex cover of size since . If we set , then this size is at most .
Thus a -approximation to the minimum vertex cover on would allows us to decide whether which, by Theorem B, is NP-hard. Thus a -approximation to the minimum vertex cover problem is NP-hard as well. (End proof.)
Computing the size of the largest independent set of a graph is called the INDSET problem.
Lemma (Approximating INDSET is hard for some ). There exists a real constant such that a -approximation to INDSET is NP-hard.
Proof sketch: Consider the graph in the preceding proof. In particular, the largest independent set of has size . If we can make a -approximation to the largest independent set problem on , we can use it to obtain a -approximation to the MAX-3CNF problem; but this is NP-hard by Theorem B. Hence a -approximation to the largest independent set problem on is NP-hard as well. (End Proof.)