NP-completeness proof

Recall that a problem $\mathcal{L}$ is NP-complete if:

• $\mathcal{L}$ can be verified in polynomial time, i.e., $\mathcal{L}\in NP$.
• Every other language in $NP$ can be polynomially reduced to that language, i.e., $\forall {\mathcal{L}}^{\prime }\in NP$, then ${\mathcal{L}}^{\prime }{\le }_P\mathcal{L}$, where ${\le }_P$ denotes a reduction from ${\mathcal{L}}^{\prime }$ to $\mathcal{L}$.

The problem is that we cannot possibly reduce every NP-complete problem to $\mathcal{L}$. Our strategy for proving $\mathcal{L}\in NPC$ is to instead reduce a known NP-complete problem to $\mathcal{L}$. The intuition behind this is that the known problem is at least as hard as our problem. Since we can reduce the known problem to our problem, any instance of the known problem can be solved by solving our problem.

For example, the MCS problem is at least as hard as the CLIQUE problem. Since you can reduce the CLIQUE problem to the MCS problem, any instance of the CLIQUE problem can be solved by solving the corresponding MCS problem instance.

The Cook-Levin theorem provides us the starting point for this approach. It proves that CIRCUIT-SAT, the circuit satisfiability problem is NP-complete. From here, we can prove that CIRCUIT-SAT reduces to other problems (CIRCUIT-SAT to BOOL-SAT to CLIQUE; from CLIQUE we can go to VERTEX-COVER or to HAM-PATH to HAM-CYCLE).

Verification

Our first step is verification, which is intuitively easy to prove (should be free marks). We’re given a possible solution to $\mathcal{L}$, and we need to prove that we can verify whether it satisfies the problem in polynomial time.