Announcements
Announcements
No Homework 6
Last Time
NP Complete/Hard
As hard as any problem in NP
Circuit SAT, 3-SAT, Maximum Independent Set are NP Complete/Hard
Lemma
A 3-SAT instance is satisfiable if and only if it is possible to select one term from each clause without selecting both a variable and its negation.
Zero-One Equations
Problem: Given a matrix A with only 0 and 1 as entries and b a vector of 1s, determine whether or not there is an x with 0 and 1 entries so that
Ax = b.
Today
NP Hardness of Knapsack and TSP
3-SAT → ZOE
Basic Idea:
Use the one term from each clause formulation of 3-SAT.
Create one variable for each term to denote whether or not it has been selected.
Add equations to enforce exactly one term from each clause, no contradictory terms selected.
Example
x1
x2
x3
x4
x5
x6
x7
One term per clause:
x1 + x2 + x3 = 1
x4 + x5 = 1
x6 + x7 = 1
No Contradictions:
x1 + x4 ≤ 1
x1 + x7 ≤ 1
x2 + x6 ≤ 1
x5 + x6 ≤ 1
Not allowed inequalities
Replace
a + b ≤ 1 with
a + b + c = 1
No Contradictions:
x1 + x4 + x8 = 1
x1 + x7 + x9 = 1
x2 + x6 + x10 = 1
x5 + x6 + x11 = 1
General Construction
Create one variable per term
For each clause, create one equation
For each pair of contradictory term, create an equation with those two and a new variable
Another Way of Looking at ZOE
Recall if A = [v1 v2 v3 … vn ],
Ax = x1 v1 + x2 v2 + x3 v3 + … + xn vn.
Example:
x1*[ 1 0 0 1 ] +
x2*[ 0 0 1 1 ] +
x3*[ 1 1 1 0 ]
—————-
= [ 1 1 1 1 ]
What if we treated these as numbers rather than vectors?
x1* 1 0 0 1 +
x2* 0 0 1 1 +
x3* 1 1 1 0
—————-
= 1 1 1 1
Reduction
If the numbers are represented in a large enough base that carrying is impossible, we have a solution to the vector equation if and only if we have a solution to the number equation.
Subset Sum
Problem: Given a set S of numbers and a target number C, is there a subset T ⊆ S whose elements sum to C.
Alternatively: Can we find xy ∈ {0,1} so that
Reduction: ZOE → Subset Sum.
Knapsack
Subset Sum is pretty closely related to (non-repeated) knapsack.
Subset Sum wants to find a set of values so that the weights equal the capacity.
Knapsack wants to find a set of values so that the weights are at most the capacity and the value is large.
Subset Sum → Knapsack
Create Knapsack problem where for each item
Value(item) = Weight(item).
Maximizing value is the same as maximizing weight (without going over capacity).
We can achieve value = capacity if and only if there is a subset of the items with total weight equal to capacity.
Knapsack is NP-Hard
3-SAT → ZOE → Subset Sum → Knapsack
Wait. Didn’t we have a polynomial time DP for knapsack?
Our algorithm was polynomial in the total weight, which in this case is exponential.
One Final Reduction
The last reduction we are going to show is
ZOE → Hamiltonian Cycle. This will show that both Hamiltonian Cycle and TSP are NP-Complete/Hard.
Strategy
Often in order to show that a problem is
NP-Complete, you want to be able to show that it can simulate logic somehow.
This is a bit difficult for Hamiltonian Cycle as most graphs have too many options, so we will want to find specific graphs with clear, binary choices.
Strategy
Start with a cycle
Double up some edges
Cycle must pick one edge from each pair.
This provides a nice set of binary variables
Need a way to add restrictions so that we can’t just use any choices.
Gadget
Must use these edges.
Two ways to fill out.
Gadget Use
Hook gadget up between a pair of edges.
Hamiltonian Cycle must use exactly one of the connected edges.
This allows us to force logic upon our choices.
Construction
By doing this for several pairs of edges we can construct Hamiltonian Cycle problems equivalent to the following:
You are given a number of choices where you need to pick one from several options (of multi-edges).
You have several constraints, that say of two choices you must have picked exactly one of them.
Example
One of these two
One of these four
One of these three
Gadget
Gadget
Gadget
Full Construction
Choices:
For each variable, choose either 0 or 1.
For each equation, choose one variable.
Constraints:
For each variable that appears in an equation, exactly one of the following should be selected:
That variable in that equation
That variable equal to 0
Example
x1+x2+x3=1
x2+x4=1
x1
x2
x3
x4
0
1
0
1
0
1
0
1
x1
x2
x3
x2
x4
Gadget
Gadget
Gadget
Gadget
Gadget
x1=1 x2=0 x3=0 x4=1
Analysis
If the ZOE has a solution, the Hamiltonian Cycle problem has a solution:
Select the values of each variable and the variables equal to 1 in each equation.
One for each and no conflicts.
If the Hamiltonian Cycle has a solution, so does the ZOE:
Set variables equal to the values selected in the cycle.
Gadgets mean that you can select a variable from an equation if and only if that variable is 1.
Must have exactly one variable from each equation equal 1.
Solution to ZOE.
Reduction Summary
Any NP Decision Problem
Circuit SAT
3-SAT
Maximum Independent Set
Zero-One
Equations
Subset Sum
Knapsack
Hamiltonian Cycle
Travelling Salesman Problem