NP and NP-completeness

NP: We have a simple proof to verify a solution

• length of proof is polynomial
• proof can be verified in polynomial time
  Cook-Levin Theorem: SAT is NP-complete

To show A is NP-complete:

1. A is in NP
2. Pick a NP-complete problem L
3. Show L reduces to A

NP: Nondeterminsitic Polynomial Time

C-hard: C can be reduced to A $\forall C \in C$
C-complete: C is in $C$.

Midterm Review

Types of problems

• Prove big-oh or not big-oh (exists…for all; for all… exists).
• Circuit family
• Fast binary conversion, Nice language, paren algorithm, sorting $\frac{3n}{2}$
• !x1, a, b; x2, b, c; !x3, c, d; (1/3 SAT)

Time Complexity, NP

• A language is in NP iff it can be decided by an NTM in polynomial time
  • Non-deterministically guess its verifier
  • Construct the verifier with the accepting path in NTM
• SAT $\in$ P iff P = NP

• 3SAT reduce to CLIQUE (triples with two exceptions)

  Cook-Levin Theorem
  SAT is NP-complete

• 3SAT is NP-c (reduce to SAT)

• CLIQUE is NP-c
• V-C is NP-c (recitation)
• HAMPATH is NP-c (3SAT, diamond, zigzag, add additional edge when $c_j$ contains $\not x_i$)
• UHAMPATH is NP-c (HAMPATH by disassembling)
• SUBSET SUM(3SAT)

Space Complexity

P $\subset$ NP $\subset$ PSPACE = NPSPACE $\subset$ EXPTIME

• If A can be decided in $t(n)$, then A has circuit complexity $t(n)^2$ (Reverse also true?)
• Circuit-SAT is NP-C
• Do exerices 9

Problems

• $HAM-CYCLE \le HAM-PATH$
  • For each edge $(u, v)$, add “tenacle” $u’ v’$.
• $TSP \le HAM-CYCLE$
  • Set weight of original edges to be $0$, others be $1$.
• $SUBSET-SUM \le 3-SAT$
  • For a $n$-var, $k$-clause 3-SAT, we build a table of vectors where lower $n$ bits, upper $k$ bits. If $x_i$ or $\not x_i$ then the lower $i$ bit is 1. If it is present in the $j$th clause, then upper $j$ is 1. For each upper column, we add two “slack rows” where one is 1, the other is 2.
  • If the $3-SAT$ is satisfiable, then we pick the rows representing true vars. We get first n bits 1s. We get each upper column 1, 2, or 3 (it cannot be 0 because there is at least 1 true var in each clause, it cannot be more than 3 because there are 3 vars in each clause). Then we pick corresponding slack rows to get all 4s on the upper bits. The reverse direction is similar.
• $3-SAT\le VC$
  • Construct a triplet for each clause, a pair for each variable $x$: $(x, \not x)$.
  • For a truth assignment, we pick 1 from the triplet to be true, the other 2 to be false. Add the false ones to the vertex cover. Add the true variable to the vertex cover. With-in edges are covered by true variables. Edges from pair to triplet have two cases. If the end in the triplet is selected(false), it is covered. If not(true), it is covered by the end in the pair.
  • For a n+2k vertex cover, 1 vertex in the triplet is not covered by itself but by the end in the pair, which is true. So this variable is true.
• $SAT\le 3-SAT$
  • Use parse tree to construct triplets with intermediate results.
• $SUBSET-SUM\le PARTITION$
  • populate $x_1, …, x_n, 2t-a$, where $a$ is the sum
• $SUBGRAPH-ISOMORPHIC$
  • CLIQUE reduces to this
• $HALTS$