Transcript NP-Complete

Friday, April 2nd Test # 2
Includes:
• Greedy Algorithms
• Nondeterministic algorithms, NP, NP-Completeness
NP-Complete
A problem npc is NP-complete if:
• npc is in NP
• Every other problem prob in NP can be transformed
in polynomial time into npc. (NP-Hard)
Transformation:
prob
Polynomial
transformation
solution
npc
How to Proof that a Problem is NPComplete?
• First problem was hard to proof: Conjunctive Normal
Form (Cook, 1971)
• Every problem q afterwards is “easier”:
Show that q is in NP
Find a problem, npc, that is NP-complete and show that
npc can be transformed in polynomial time into q
TSP
Shortest Path
Sorting
MST
npc
q
…
Knapsack
What Does this Thing “Polynomial
Transformation” Means?
A problem A can be transformed in polynomial time into a
problem B if we can write a polynomial algorithm that transforms
A into B such that when we solve B, we also solve A
A
B
Example:
A: Find a Maximum Spanning Tree of an input graph G
B: Find a Minimum Spanning Tree of an input graph G
Transformation from A into B:
Multiply the weight of each edge in G by -1
Conjunctive Normal Form
A conjunctive normal form (CNF) is a Boolean expression
consisting of one or more disjunctive formulas connected by an
AND symbol (). A disjunctive formula is a collection of one or
more (positive and negative) literals connected by an OR
symbol ().
Example:
(a)  (¬ a  ¬b  c  d)  (¬c  ¬d)  (¬d)
Problem (CNF-satisfaction): Give an algorithm that
receives as input a CNF form and returns Boolean
assignments for each literal in form such that form is true
Example (above):
a  true, b  false, c  true, d  false
Cook Theorem (1971)
The CNF-satisfaction satisfaction is NP-complete
(Vague) Idea of The Proof (I)
State1: S1
State2: S2
Computer Memory
S2
S1
S1
S2
Program
…
<instruction>
….
A computation: S1, S2, S3, …, Sm
(Vague) Idea of The Proof (II)
Statej
Computer Memory
Sj
Sj
Program
…
<instruction>
….
Sj can be represented as a logic formula Fj
The computation can be represented S1, S2, S3, …, Sm as
(F1  F2  …  Fm), which is transformed into a CNF
The Issue with the “Cheating”
phaseII(C: path, min: int )
//input: C a guessed solution
//output: true iff C is a TSP
If |C| < n then return false
Visited  {}
for i =1 to n do {
(u,v) = C[i]
if v in Visited then
return false
else Visited  Visited + {v}
}
return cost(C) = min
How can we know the
minimum cost in advance?
•The concept of nondeterministic
algorithms is not for solving actual
problems.
•This concept is useful for
determine properties about the
problems (e.g., NP-completeness)
•When transforming problems into
other problems we formulate
problems as decision problems
Decision Problems
A decision problem is one that has a Yes or No answer
Standard Formulation
Decision Problem Formulation
Find the position of 3 in the
array A[1..N]
Is the element 3 in the array
A[1..N]?
Find the minimum number in
the array A[1..N]
Find a minimum spanning tree
for a graph G
Is m the minimum number in the
array A[1..N]?
Is there a minimum spanning tree
G of cost m?
Find a Traveling Salesman
Solution for a graph G
Is there a Traveling salesman
solution for G of cost m?
Note that the nondeterministic algorithms return True or False
Circuit-sat (I)
A Boolean combinatorial circuit consists of one or more
Boolean components connected by wires such that there is
one connected component (i.e., there are no separate parts)
and the circuit has only one output. Boolean components:
x
y
x
y
x
xy
xy
¬x
Circuit-sat (II)
Circuit-sat: Given a Boolean combinatorial circuit, find a
Boolean assignment of the circuit’s input such that the
output is true
x
y
z
Homework
• Show that Circuit-sat is NP-complete
CNF
Circuit-SAT
Show that Circuit-sat is in NP
Show that CNF can be polynomial transformed into Circuit-sat
Consider the formulas:
(a)  (¬a  ¬b  c  d)  (¬c  ¬d)  (¬d) (Section 010)
( a  ¬b)  (c  ¬b)  (d  ¬b)  b
(Section 011)
a. For which assignments is the formula true?
b. Draw the formula in an equivalent circuit
c. Explain in words how the transformation is done
•Section 010:
Formulate the Hamiltonian circuit as a decision problem
 show that Graph Coloring is in NP (pseudocode!)
•Section 011:
 Formulate Graph Coloring as a decision problem
 Show that the Hamiltonian Circuit is in NP (pseudocode!)