Lecture 6

NP-completeness

$P$: Polynomial-time Solvable

$P$: Class of decision problems $L$ such that there is a polynomial-time algorithm that correctly answers yes or not for every instance $l\in L$.

Algorithm "$A$ decides $L$". If algorithm $A$ always correctly answers for any instance $l\in L$.

Example:

Is the number $n$ prime? Best algorithm so far: $O(\log^6 n)$, 2002

Introduction to NP

• NP$\neq$ Non-polynomial (Non-deterministic polynomial time)
• Let $L$ be a decision problem.
• Let $l$ be an instance of the problem that the answer happens to be "yes".
• A certificate c(l) for $l$ is a "proof" that the answer for $l$ is true. [$l$ is a true instance]
  • For canonical decision problems for optimization problems, the certificate is often a feasible solution for the corresponding optimization problem.

Example of certificates

• Problem: Is there a path from $s$ to $t$
  • Instance: graph $G(V,E),s,t$.
  • Certificate: path from $s$ to $t$.
• Problem: Can I schedule $k$ intervals in the room so that they do not conflict.
  • Instance: $l:(I,k)$
  • Certificate: set of $k$ non-conflicting intervals.
• Problem: ISET
  • Instance: $G(V,E),k$.
  • Certificate: $k$ vertices with no edges between them.

If the answer to the problem is NO, you don't need to provide anything to prove that.

Useful certificates

For a problem to be in NP, the problem need to have "useful" certificates. What is considered a good certificate?

• Easy to check
  • Verifying algorithm which can check a YES answer and a certificate in $poly(l)$
• Not too long: [$poly(l)$]

Verifier Algorithm

Verifier algorithm is one that takes an instance $l\in L$ and a certificate $c(l)$ and says yes if the certificate proves that $l$ is a true instance and false otherwise.

$V$ is a poly-time verifier for $L$ is it is a verifier and runs in $poly(|l|,|c|)$ time. (c=$poly(l)$)

• The runtime must be polynomial
• Must check every problem constraint
• Not always trivial

Class NP

NP: A class of decision problems such that exists a certificate schema $c$ and a verifier algorithm $V$ such that:

1. certificate is $poly(l)$ in size.
2. $V:poly(l)$ in time.

P: is a class of problems that you can solve in polynomial time

NP: is a class of problems that you can verify TRUE instances in polynomial time given a poly-size certificate

Millennium question

$P\subseteq NP$? $NP\subseteq P$?

$P\subseteq NP$ is true.

Proof: Let $L$ be a problem in $P$, we want to show that there is a polynomial size certificate with a poly-time verifier.

There is an algorithm $A$ which solves $L$ in polynomial time.

Certificate: empty thing.

Verifier: $(l,c)$

1. Discard $c$.
2. Run $A$ on $l$ and return the answer.

Nobody knows the solution $NP\subseteq P$. Sad.

Class of problem: NP complete

Informally: hardest problem in NP

Consider a problem $L$.

• We want to show if $L\subseteq P$, then $NP\subseteq P$

NP-hard: A decision problem $L$ is NP-hard if for any problem $K\in NP$, $K\leq_p L$.

$L$ is at least as hard as all the problems in NP. If we have an algorithm for $L$, we have an algorithm for any problem in NP with only polynomial time extra cost.

MindMap:

$K\implies L\implies sol(L)\implies sol(K)$

Lemma $P=NP$

Let $L$ be an NP-hard problem. If $L\in P$, then $P=NP$.

Proof:

Say $L$ has a poly-time solution, some problem $K$ in $NP$.

For any $K\in NP$, $NP\subset P$, $P\subset NP$, then $P=NP$.

NP-complete: $L$ is NP-complete if it is both NP-hard and $L\in NP$.

NP-optimization: $L$ is NP-optimization problem if the canonical decision problem is NP-complete.

Claim: If any NP-optimization problem have polynomial-time solution, then $P=NP$.

Is $P=NP$?

• Answering this problem is hard.
• But for any NP-complete problem, if you could find a poly-time algorithm for $L$, then you would have answered this question.
• Therefore, finding a poly-time algorithm for $L$ is hard.

NP-Complete problem

Satisfiability (SAT)

Boolean Formulas:

A set of Boolean variables:

$x,y,a,b,c,w,z,...$ they take values true or false.

A boolean formula is a formula of Boolean variables with and, or and not.

Examples:

$\phi:x\land (\neg y \lor z)\land\neg(y\lor w)$

$x=1,y=0,z=1,w=0$, the formula is $1$.

SAT: given a formula $\phi$, is there a setting $M$ of variables such that the $\phi$ evaluates to True under this setting.

If there is such assignment, then $\phi$ is satisfiable. Otherwise, it is not.

Example: $x\land y\land \neg(x\lor y)$ is not satisfiable.

A seminar paper by Cook and Levin in 1970 showed that SAT is NP-complete.

1. SAT is in NP
   Proof:
   $\exists$ a certificate schema and a poly-time verifier.
   $c$ satisfying assignment $M$ and $v$ check that $M$ makes $\phi$ true.
2. SAT is NP-hard. we can just accept it has a fact.

How to show a problem is NP-complete?

Say we have a problem $L$.

1. Show that $L\in NP$.
   Exists certificate schema and verification algorithm in polynomial time.
2. Prove that we can reduce SAT to $L$. $SAT\leq_p L$ (NOT $L\leq_p SAT$) Solving $L$ also solve SAT.

CNF-SAT

CNF: Conjugate normal form of SAT

The formula $\phi$ must be an "and of ors"

$l_{i,j}$: clause

3-CNF-SAT

3-CNF-SAT: where every clauses has exactly 3 literals.

is NP complete [not all version of them are, 2-CNF-SAT is in P]

Input: 3-CNF expression with $n$ variables and $m$ clauses in the form:

number of total literals: $3m$

Output: An assignment of the $n$ variables such that at least one literal from each clauses evaluates to true.

Note:

1. One variable can be used to satisfy multiple clauses.
2. $x_i$ and $\neg x_i$ cannot both evaluate to true.

Example: ISET is NP-complete.

Proof:

Say we have a problem $L$

1. Show that $ISET\in NP$
   Certificate: set of $k$ vertices: $|S|=k\in poly(g)$
   Verifier: checks that there are no edges between them $O(E k^2)$
2. ISET is NP-hard. We need to prove $3SAT\leq_p ISET$
   • Construct a reduction from $3SAT$ to $ISET$.
   • Show that $ISET$ is harder than $3SAT$.

We need to prove $\phi\in 3SAT$ is satisfiable if and only if the constructed $G$ has an $ISET$ of size $\geq k=m$

Reduction mapping construction

We construct an ISET instance from $3-SAT$.

Suppose the formula has $n$ variables and $m$ clauses

1. for each clause, we construct vertex for each literal and connect them (for $x\lor \neg y\lor z$, we connect $x,\neg y,z$ together)
2. then we connect all the literals with their negations (connects $x$ and $\neg x$)

$\implies$

If $\phi$ has a satisfiable assignment, then $G$ has an independent set of size $\geq m$,

For a set $S$ we pick exactly one true literal from every clause and take the corresponding vertex to that clause, $|S|=m$

Must also argue that $S$ is an independent set.

Example: picked a set of vertices $|S|=4$.

A literal has edges:

• To all literals in the same clause: We never pick two literals form the same clause.
• To its negation.

Since it is a satisfiable 3-SAT assignment, $x$ and $\neg x$ cannot both evaluate to true, those edges are not a problem, so $S$ is an independent set.

$\impliedby$

If $G$ has an independent set of size $\geq m$, then $\phi$ is satisfiable.

Say that $S$ is an independent set of $m$, we need to construct a satisfiable assignment for the original $\phi$.

• If $S$ contains a vertex corresponding to literal $x_i$, then set $x_i$ to true.
• If contains a vertex corresponding to literal $\neg x_i$, then set $x_i$ to false.
• Other variables can be set arbitrarily

Question: Is it a valid 3-SAT assignment?

Your ISET $S$ can contain at most $1$ vertex from each clause. Since vertices in a clause are connected by edges.

• Since $S$ contains $m$ vertices, it must contain exactly $1$ vertex from each clause.
• Therefore, we will make at least $1$ literals form each clause to be true.
• Therefore, all the clauses are true and $\phi$ is satisfied.

Conclusion: NP-completeness

• Prove NP-Complete:
  • If NP-optimization, convert to canonical decision problem
  • Certificate, Verification algorithm
  • Prove NP-hard: reduce from existing NP-Complete problems
• 3-SAT Problem:
  • Input, output, constraints
  • A well-known NP-Complete problem
  • Reduce from 3-SAT to ISET to show ISET is NP-Complete

On class

NP-complete

$p\in NP$, if we have a certificate schema and a verifier algorithm.

NP-complete proof

P is in NP

what a certificate would looks like, show that if has a polynomial time o the problem size.

design a verifier algorithm that checks a certificate if it indeed prove tha the answer is YES and has a polynomial time complexity. Inputs: certificate and the problem input $poly(|l|,|c|)=poly(|p|)$

P is NP hard

select an already known NP-hard problem: eg. 3-SAT, ISET, VC,...

show that $3-SAT\leq_p p$

• present an algorithm that given any instance of 3-SAT (on the chosen NP hard problem) to an instance of $p$.
• show that the construction is done in polynomial time.
• show that if $p$'s instance answer is YES, then the instance of 3-SAT is YES.
• show that if 3-SAT's instance answer is YES then the instance of $p$ is YES.