CSCE 411 Lecture 32

Lecture Slides

« previous | Monday, November 12, 2012 | next »

NP-Completeness

1. $L\in NP$
2. $L'\leq _{p}L\forall L'\in NP$

Suppose $L$ is NP-complete

1. If there is a poly time algorithm for $L$, then $P=NP$
2. If there is no poly time algorithm for $L$, then $P\neq NP$

Showing NP-Completeness

Direct approach:

1. Show $L\in NP$
2. Show that every other language in NP is polinomially reducible to $L$.

Better approach:

1. Show $L\in NP$
2. Choose appropriate known NP complete language $L'$
3. Show $L'\leq _{p}L$

Works by transitivity.

First NP-Complete Problem

Satisfiability problem (SAT): given a boolean function, is there a set of true and false inputs that will return true?

First, some vocab:

Boolean variables

take on values T or F (e.g. $x,y$)

Literal

a variable or a negation or a variable (e.g. $x,\neg x$)

Clause

disjunction (OR) of several literals $x\vee \neg y\vee z\vee \neg w$

Conjunctive Normal Form (CNF) formula

is a conjunction (AND) of several clauses (e.g. $(\neg x\vee y)\wedge (\neg z\vee \neg w\vee x)$

Is $x\vee \neg y$ satisfiable? (Yes, $x=T$, $y=F$

A formula that has $n$ variables has $2^{n}$ possible inputs.

SAT is NP-Complete

SAT is in NP: it's hard to find a solution, but when given a solution, checking it is easy. Just plug it into the function.

Show every language in NP is polynomially reducible to SAT.

key idea: each NP language is solved by some nondeterministic Turing machine in polynomial time.

Given a description of a poly time TM, construct in poly time, a CNF formula that simulates the computation of the turing machine.

3SAT

A special case of SAT: each clause contains exactly 3 literals

3SAT is in NP because SAT is in NP

Is 3SAT NP-complete? Regular structure may be exploited to obtain poly algorithm. (e.g. 2SAT has poly time algorithm)

1. Use same truth-assignment algorithm as SAT to verify solution
2. Use SAT as NP-complete problem
3. reduce 3SAT problem to SAT problem in poly time such that SAT problem is satisfiable iff 3SAT is satisfiable

Reduction

Reduction requires some simple boolean algebra:

Given CNF formula of $m$ clauses over set of vars $U$, replace each clause with a set of 3-clauses, and may use some extra variables.

Let $c_{i}=z_{1}\wedge \dots \wedge z_{k}$.

Case $k=1$: use 2 extra variables $y_{i}^{1}$ and $y_{i}^{2}$ to replace $c_{i}$ with 4 clauses:

• $(z_{1}\vee y_{i}^{1}\vee y_{i}^{2})$
• $(z_{1}\vee \neg y_{i}^{1}\vee y_{i}^{2})$
• $(z_{1}\vee y_{i}^{1}\vee \neg y_{i}^{2})$
• $(z_{1}\vee \neg y_{i}^{1}\vee \neg y_{i}^{2})$

Case $k=2$: use 1 extra variable $y_{i}^{1}$ to replace $c_{i}$ with 2 clauses:

• $(z_{1}\vee z_{2}\vee \neg y_{i}^{1})$
• $(z_{1}\vee z_{2}\vee y_{i}^{1})$

Case $k=3$: no work necessary

Case $k>3$: use $k-2$ variables $y_{i}^{1},\ldots y_{i}^{k-3}$ to replace $c_{i}$ with $k-2$ clauses:

• $(z_{1}\vee z_{2}\vee y_{i}^{1})$
• $(\neg y_{i}^{1}\vee z_{3}\vee y_{i}^{2})$
• $(\neg y_{i}^{2}\vee z_{3}\vee y_{i}^{3})$
• ...
• $(\neg y_{i}^{k-4}\vee z_{k-2}\vee y_{i}^{k-3})$
• $(\neg y_{i}^{k-3}\vee z_{k-1}\vee z_{k})$

Is Reduction Poly Time?

Running time of reduction is proportional to the size of SAT problem.

Size of new formula is constant factor larger than original formula:

• 1 literal → 4 clauses
• 2 literals → 2 clauses
• 3 literals → 1 clause
• 4+ literals → $k-2$ clauses

Note: Minesweeper is NP-complete: given a configuration of numbers, can we find placement of mines that is coherent with those numbers?