CSCE 411 Lecture 32

Lecture Slides

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

NP-Completeness

1. $L\in NP$
2. $L^{\prime }{\le }_{p}L\mathrm{\forall }{L}^{\prime }\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\ne 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^{\prime }$
3. Show $L^{\prime }{\le }_{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,\mathrm{\neg }x$)

Clause

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

Conjunctive Normal Form (CNF) formula

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

Is $x\vee \mathrm{\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 \mathrm{\neg }{y}_i^1\vee y_i^2)$
• $(z_1\vee y_i^1\vee \mathrm{\neg }{y}_i^2)$
• $(z_1\vee \mathrm{\neg }{y}_i^1\vee \mathrm{\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 \mathrm{\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,\dots y_i^{k-3}$ to replace $c_i$ with $k-2$ clauses:

• $(z_1\vee z_2\vee y_i^1)$
• $(\mathrm{\neg }{y}_i^1\vee z_3\vee y_i^2)$
• $(\mathrm{\neg }{y}_i^2\vee z_3\vee y_i^3)$
• ...
• $(\mathrm{\neg }{y}_i^{k-4}\vee z_{k-2}\vee y_i^{k-3})$
• $(\mathrm{\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?