NP-completeness

Intro

A decision problem $X$ is NP-complete (NPC) if $X \in NP$ and $X \in NP-hard$.

Certificate and Certifier

Algorithm $C(s, t)$ is a certifier for problem $X$ if $\forall$ string s, $s \in X$ iff $\exists$ a string t (certificate) such that $C(s, t) = yes$.

Ex. 3-SAT Given a CNF formula $\phi$, is there a satisfying assignment?

• Certifier:

  Check each clause in $\phi$ has least one true literal

• Certificate:

  a solution (assignment to boolean variables) that

  satisfies $\phi$

• instance $s$: $\phi = (\overline{x_1} \lor x_2 \lor x_3) \land (x_1 \lor \overline{x_2} \lor x_3) \land (\overline{x_1} \lor x_2 \lor x_4)$

• certificate t: $x_1 = true, x_2 = true, x_3 = false, x_4 = false$

Reduction

A reduction from problem A $\rightarrow$ problem B is to construct a polynomial time algorithm that converts A inputs $\rightarrow$ equivalent B inputs (same yes/no answer). If we know how to solve B, then we know how to solve A. So if $B \in P$, then $A \in P$. If $B \in NP$, then $A \in NP$. B is at least as hard as A. (A $\leq_p$B)

Prove NPC

It's good to know so we can give up on searching a polynomial algorithm for this problem ᵔᴥᵔ. So how do we prove a problem $X$ is NP-complete? 1. $X \in NP$ (give a certificate and a ploy-time certifier) 2. reduce from a known NPC problem (3-SAT is a good choice for almost anything)

Cook and Levin did all the ground work to prove Circuit-SAT and 3-SAT are NPC. Here we are just gonna show NPC with reduction.

Prove 3-SAT is NPC

We need a poly-time certifier to check a certificate of 3-SAT. Therefore, 3SAT $\in NP$.

Now we need to pick a known NPC problem and show 3-SAT is harder. We decide to reduce from Circuit-SAT to 3-SAT (Circuit-SAT $\leq_p$3-SAT). We want to construct a poly-time algorithm that converts C-S inputs to 3-SAT inputs such that a 3-SAT instance $\phi$ is satisfiable iff the C-S inputs have an output of 1.

The conversion algorithm has 3 steps.

Reduction Proof Let $K$ be any circuit

$\Leftarrow$ there are inputs of $K$ that have output 1. can convert input values to create values at all nodes of $K$. This input satisfies $\phi$.

$\Rightarrow$ $\phi$ is satisfiable. 3-SAT clauses were designed to ensure the values assigned to all nodes in $K$ match exactly what the circuit would compute.

Reference

Algorithm Design Chapter 8 Intractability