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$

Basics

• Regular: all nodes have same degrees
• Walk
• Path: Walk with no repeated vertices
• Cycle: a walk from u to u where the only repeated vertex is u
• Tree: connected; n-1 edges; acyclic
• Local Search guarantees to get $\ge \frac{m}{2}$
  • Each vertex has $\ge \frac{deg(v)}{2}$ edges cut because otherwise we can flip its color to get more cuts

Problem: Identify all nodes reachable from s.
BFS, DFS, AFS
AFS finds a spanning tree rooted at s (bag, mark)
Why does AFS halt?
If we put edge in the bag, get a spanning tree.
Full AFS finds all connected components
CFS: Cheapest First Search
MST: subset of edges of minimum total cost such that all vertices connected
Prim: put the cheapest edge in the bag. If use Priority Queue, $O(Elog(E))$ run-time.
MST Cut Property e is the cheapest edge from S to not S, then must be in the MST.
Kruskal: Go through edges, add as long as it does not make cycles
Boruvka: Add the cheapest edges out of each c.c.

Matching

Bipartite Graph: there is a bipartition X and Y such that each edge connects x and y.
Matching: a subset of edges that do not share an endpoint.
Maximum Matching: A matching with largest number of edges
Perfect Matching: A matching that covers all vertices
Stable matching: There is no unstable pair(u, v not matched to each other, but they prefer each other to their current partners)
GS-algorithm: While a man is unmatched: propose to w(highest in the list)

• $O(n^2)$ (because number of proposals are $n^2$).
• Perfect Matching
• Stable
  GS always finds the Best Valid Partner
  Prove: Man always finds the best. Woman always finds the worst.

Maximum Matching

Augmenting path(with respect to matching M): edges alternate between in M and not in M.
Prove: If there is an aug. path, M is not maximum
Find Maximum Matching: start with an edge, find augment path, …
To find aug. path: direct edges in M from left to right.

Strong Church-Turing Thesis: The intuitive notion of “efficiently computable” is captured by functions efficiently computable by a TM.

• Master Method
  For $T(n) \le a\dot T(\frac{n}{b}) + O(n^d)$,
  • $a = b^d$, $O(n^dlog n)$
  • $a < b^d$, $O(n^d)$
  • $a > b^d$, $O(n^{log_ba})$

Polynomial time and the class P

$DTIME(T(n)) = $ the language decided by an $O(T(n))$ time algorithm.
$P=DTIME(n^k)$ union of all
$EXP=DTIME(2^{n^k})$ union of all
P is a subset of EXP.
We can prove that Polynomial time algorithms can solve every decidable problem
$HWTB$ is the language such that M takes at most $n^3$ steps. This cannot be decided in $O(n^2)$ steps, which can be proved with diagonalization algorithm.
Time Hierarchy Theorem
Let $T(n)$ be a time-constructible algorithm. $\epsilon > 0$. Then there is a problem which cannot be decided in time $T(n)$, but can be decided in time $T(n)^{1+\epsilon}$. $DTIME(T(n))$ is a PROPER subset of $DTIME(T(n)^{1+\epsilon})$.

Space Complexity

• Use two-tape TM that has a work tape and an input tape that is read-only.
  $DSPACE(T(n)) = $ the language decided by an $O(T(n))$ space algorithm.
  PSPACE, L is log space. L is a subset of PSPACE.
  Space Hierarchy Theorem
  If a TM uses $S(n)\ge log_2(n)$, then it decides the language using $\le 2^{O(S(n))}$ time (because of the number of possible configurations)
• $L\subset P$
• $PSPACE\subset EXP$
  Circuit Complexity
  A circuit family is an infinite answer to infinite number of questions
• The size of a circuit is the total number of gates, including inputs as gates too
• Circuit complexity is the size of the minimal circuit family that decides the language
  Circuit complexity is ALWAYS bounded by $2^n$.
  $f_A(x_1, x_2, …, x_n) = (x_1\wedge f_A(1, x_2, …, x_n))\wedge (\not x_1\wedge (f_A(0, x_2, .., x_n)))$
  This has recurrence $s(n) \le 2s(n-1)+5$.
  W.T.S.: There is a language L whose circuit complexity is at least $2^n/4n$.

1. Number of possible functions is $2^{2^n}$
2. Number of circuits of size s is $\le 2^{4slogs}$
   Claim 2: for each gate, 2 bits for its type, 2logs bits for which gates the inputs are from.