NP-Completeness (1)

Polynomial time algorithms

• Inputs of size $n$, worst case time is $O(n^k)$ for some constant $k$
• All problems cannot be solved in polynomial time

---

NP-Complete problem

NP-Complete problems

• Status is unknown
• No polynomial time algorithm has yet been discovered
  nor has anyone yet been able to prove that no polynomial time algorithm can exist for any one of them

---

Class P

• Problems that are solvable in polynomial time $O(n^k)$ for some constant $k$

Class NP

• Problems that are verifiable in polynomial time
• Verifiable?
  • If we were somehow given a certificate of a solution,
    then we could verify that the certificate is correct in polynomial time

Example

• Hamiltonian cycle
  • Hamiltonian cycle of an undirected graph $G=(V,E)$ is a simple cycle that contains every vertex in $V$
  • Does $G$ have a Hamiltonian cycle?
  • Certificate is a sequence $<v_1, v_2, \dots, v_{|V|}>$ of $|V|$ vertices
  • We could check in polynomial time that $(V_i, V_{i+1})\in E$ for $i=1,2,\dots,|V|$ and $(V_{|V|}, V_1) \in E$

Class P vs Class NP

• P $\sube$ NP
• The open question is whether or not P is a proper subset of NP. P=NP?

---

Class NPC

• A problem is in NP and is as hard as any problem in NP
• If any NP-complete problem can be solved in polynomial time,
  then every problem in NP has a polynomial time algorithm
• When we demonstrate that a problem is NP-complete,
  we are making a statement about how hard it is

How to solve a problem

• Usually can cast a given optimization problem as a related decision problem by imposing a bound on the value to be optimized
• What is the shortest path length from $u$ to $v$?
  $\Rightarrow$ Is there a path from $u$ to $v$ with length $\leq k$?
• Decision problem is in a sense easier or at least no harder than the optimization problem

---

Reduction

Reduction

• Let a decision problem $A,B$
• Suppose that we have a procedure that transforms any instance $\alpha$ of $A$ into some instance $\beta$ of $B$ such that
  • The transformation takes polynomial time
  • The answer for $\alpha$ is same as the answer for $\beta$
• We call such a procedure a polynomial time reduction algorithm
• If such a reduction algorithm exist,
  we say $A$ is reducible to $B$ and denote it by $A\leq_pB$

Reduction Algorithm

• Given an instance $\alpha$ of $A$, use a polynomial time reduction algorithm to transform it to an instance $\beta$ of $B$
• Run the polynomial-time decision algorithm for $B$ on $\beta$
• Use the answer for $\beta$ as the answer for $\alpha$

• If there is no polynomial time algorithm can exist for $A$,
  and A polynomial time reduction algorithm exist for transforming instances of $A$ to instances of $B$,
  No Polynomial time algorithm can exist for $B$

Reducibility

• A problem $Q$ can be reduced to another problem $Q'$
  if any instance of $Q$ can be easily rephrased as an instance of $Q'$,
  the solution to which provides a solution to the instance of $Q$

Example

• Solving linear equations in an indeterminate $x$ reduces to the problem of solving quadratic equations
• Given an instance $ax+b=0$, we transform it to $0x^2+ax+b=0$, whose solution provides a solution to $ax+b=0$
• Thus if a problem $Q$ reduces to another problem $Q'$,
  then $Q$ is no harder to solve than $Q'$

---

Definition

A problem $A$ is NP-Hard

• If we can solve this problem in polynomial time,
  we can solve all NP problems in polynomial time
  ($A'\leq_pA$ all $A' \in NP$)

A problem $A$ is NP-Complete

• It is in NP
• It is NP-Hard
  • $A'\leq_pA$ all $A' \in NP$
  • Alternatively, $A'\leq_pA$ for some known NP-Complete problem $A'$
• If any one is solvable in polynomial time, then they all are
• Conversely, if any one is not solvable in polynomial time, then none are
• Once there is any one problem that is proved NP-complete, we can use polynomial time reducibility as a tool to prove other problems to be NP-complete

---

Example

Circuit-SAT Problem

Circuit-SAT Problem

• What is the input that makes a true output?

Lemma

• Circuit satisfiability problem belongs to the class NP, NP-Hard
  $\Rightarrow$ Circuit-SAT problem is NP-Complete

---

SAT Problem

• Input: A boolean formula
• Question: Is there some way to assign truth value to the variables so that the formula evaluates to true?

Lemma

• SAT problem is NP-Complete

Cook's Theorem

• SAT is NP-Complete
  • Circuit-SAT $\leq_p$ SAT

---

3-CNF-SAT Problem

• Input: A boolean formula in 3-conjunctive normal form
• Question: Operations in clause are OR,
  operations outside the clause are AND.

---

CLIQUE

Clique

• A clique in an undirected graph $G=(V,E)$ is a subset $V' \sube V$ of vertices,
  each pair of which is connected by an edge in $E$
• A clique is a complete subgraph of $G$

Optimization problem

• Input: An undirected graph $G=(V,E)$
• Question: Find a clique of maximum size in a graph

Decision problem

• Input: An undirected graph $G=(V,E)$ and an integer $k$
• Question: Is there a clique of a given size $k$ in the graph?

Naive algorithm

• Check whether a sub-graph of size $k$ forms a clique
  • Running time is $\Omega(k^2 \times \begin{pmatrix} |V| \\ k \end{pmatrix})$ which is polynomial if $k$ is a constant
  • In general, however, $k$ could be near $|V|/2, \Rightarrow$ superpolynomial

---

CLIQUE (NPC proof)

1. Problem is NP

• Clique $\in$ NP for a given graph $G=(V,E)$
  • Use the set $V' \sube V$ of vertices in the clique as a certificate of $G$
  • Checking whether $V'$ is a clique can be accomplished in polynomial time
    by checking whether for each pair $u,v \in V'$, the edge $(u,v)$ belong to $E$

2. Problem is NP-Hard

• 3-CNF-SAT $\leq_p$ CLIQUE (CLIQUE is NP-Hard)
  1. The reduction algorithm begins with an instance of 3-CNF-SAT
  • Logical formula $\rightarrow$ Graph
  • 모든 vertex 연결
    • 자기 자신의 not 인 경우 X
    • 같은 괄호 안의 vertex 끼리 X
      
    • $k$ = 3 (괄호의 개수)
  2. Show that this transformation of $\phi$ into $G$ is a reduction
  • For each clause $C_r=(l_1^r \lor l_2^r \lor l_3^r) \text{ in } \phi$,
    replace a triple of vertices $v_1^r,v_2^r,v_3^r$ into $V$
  • 3-CNF-SAT $\rightarrow$ CLIQUE
    • Output이 true 이려면 clause 마다 literal 하나씩은 true 이어야함
    • 자신의 not 과는 edge 를 생성하지 않았기 때문에 3-clique 생성됨
  • CLIQUE $\rightarrow$ 3-CNF-SAT
    • 3-clique이 있다는 것은 clause 마다 반드시 하나씩 선택됨
    • 선택된 edge는 vertex와 그의 not 이 존재할 수 없기 때문에 3-CNF-SAT 도 true