Complexity Theory: Reductions and NP-Completeness Proofs

Vertex Cover ≤ CLIQUE

Suppose G has a clique S with |S| = k. Consider S' = V – S. Then, |S'| = |V| - k. To show S' is a cover, consider any edge (v, w) ∈ E'. Then, (v, w) ∉ E, at least one of v or w is not in S (since S forms a clique), and at least one of v or w is in S'; hence, (v, w) is covered by S'.

Suppose G' has a cover S' with |S'| = |V| - k. Consider S = V – S'. Clearly, |S| = k. To show S is a clique, consider some edge (v, w) ∈ E'. Then, if (v, w) ∈ E', either v ∈ S', w ∈ S', or both. By contrapositive, if v ∉ S' and w ∉ S', then (v, w) ∈ E; thus, S is a clique in G.

Vertex Cover ≤ SET COVER

Given a black box that solves instances of SET-COVER, let G = (V, E) and k be an instance of VERTEX-COVER. Create a SET-COVER instance: k = k, U = E, S_v = {e ∈ E : e incident to v}. Therefore, a set-cover of size at most k exists if and only if a vertex cover of size at most k exists.

SAT ≤ 3-SAT

Suppose the SAT instance is satisfiable. If the SAT assignment sets t_jk = 1, the 3-SAT assignment sets: t_jk = 1, y_m = 1 for all m < k, and y_m = 0 for all m ≥ k.

Suppose the 3-SAT instance is satisfiable. If the 3-SAT assignment sets t_jk = 1, the SAT assignment sets t_jk = 1. Consider clause C_j. We claim t_jk = 1 for some k. Then, each of l - 1 new Boolean variables y_j can only make one of l new clauses true, and the remaining clause must be satisfied by an original term t_jk.

SAT ≤ CLIQUE

Given an instance of CNF-SAT, create a node for each literal in each clause. Two nodes are connected if they do not come from the same clause and do not represent a literal and its negation. A clique of size C implies a satisfiable assignment. A satisfiable assignment implies a clique of size C such that (x, y, z) = (true, true, false). We can then choose one true literal from each clause to complete the proof.

Proof that VC ∈ NP

On input <G, k>, where G = (V, E):

• Guess a subset C = {v₁, v₂, …, v_k} of V.
• For each edge {u, v} ∈ E: If u ∉ C and v ∉ C, then REJECT.
• ACCEPT.