23. NP-Complete

Mar 29/31, 2022

Polynomial time reductions

Polynomial computable function $f$: there exists a Turing machine $M$ such that for any string $w$ computes $f(w)$ in polynomial tine $O(|w{|}^k)$.

Observation: the length of $f(w)$ is bounded $|f(w)|=O(|w{|}^k)$, since $M$ cannot use more than $O(|w{|}^k)$ tape space in time $O(|w{|}^k)$.

Definition. Language A is polynomial time reducible to language B if there is a polynomial computable function $f$ such that $w\in a\iff f(w)\in B$.

Theorem. Suppose that $A$ is polynomial time reducible to $B$. If $B\in P$ then $A\in P$.

Proof. Let $M$ be the machine that decides B in polynomial time. Construct machine $M^{{}^{\prime }}$ to decide $A$ in polynomial time. On input string $w$:

1. Compute $f(w)$
2. Run $M$ on input $f(w)$
3. If $f(w)\in B$ then accept $w$.

Reducing 3CNF to CLIQUE

3CNF

• each clause has 3 literals e.g. $(x_1\vee \overline{x_2}\vee \overline{x_3})\wedge (x_3\vee \overline{x_5}\vee x_6)\wedge \dots$
• language: 3CNF-SAT = { $w$ : $w$ is a satisfiable 3CNF formula }

Clique

• Language: CLIQUE = { $<$ $G,k$ $>$: graph $G$ contains a $k$-clique }

Theorem: 3CNF-SAT is P-time reducible to CLIQUE

Proof. give a polynomial time reduction of one problem to another.

Transform formula to graph: if formula is satisfied, graph will have k-size clique $\iff$ is graph has $k$-size clique, then formula is satisfiable. Steps:

1. for each 3CNF clause, create a node for each of its variables
2. Add a link from a literal $l$ to a literal in every other clause, except its complement $\bar{l}$
3. The formula is satisfied iff the graph has a k-clique

NP-Complete languages

We define the class of NP-complete languages:

╭——————————————————————╮
│      Decidable       │
│ ╭—————————————————╮  │
│ │       NP        │  │
│ │ ╭—————————————╮ │  │
│ │ │ NP-Complete │ │  │
│ │ ╰—————————————╯ │  │
│ ╰—————————————————╯  │
╰——————————————————————╯

Every problem in NP can be transformed in P time to any NP-complete problem, i.e. a language $L$ is NP-complete if: (1) L is in NP and (2) every language in NP is reduced to L in P-time. If a NP-complete language is proven to be in P, then P=NP.

Theorem. If language $A$ is NP-complete, and language $B$ is in NP, and $A$ is polynomial time reducible to $B$ => then $B$ is NP-complete.

Proof. Any language $L$ in NP is polynomial time reducible to $A$. Thus $L$ is polynomial time reducible to $B$.

Cook-Levin Theorem

Language SAT (satisfiability problem) is NP-complete.

Proof. Part 1: SAT is in NP (proven previously). Part 2: reduce all NP languages to the SAT problem in polynomial time.

Take an arbitrary language $L\in NP$. We will give a P-time reduction of $L$ to SAT. Let $M$ be nondeterministic TM that decides L in P-time.

Provable by construction: for any string $w$, we can construct in P-time a Boolean expression $\varphi (M,w)$ such that $w\in L\iff \varphi (M,w)$ is satisfiable.

• SAT is free-form Boolean expression

• CNF (conjunctive normal form) contains clauses of Boolean expressions

  • 3CNF is case of exactly 3 literals in each clause
  • CNF form can be converted to 3CNF in P time

• SAT, CNF-SAT, 3CNF-SAT are NP-complete languages => known as NP-languages