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:
x
1
*[ 1 0 0 1 ] +
x
2
*[ 0 0 1 1 ] +
x
3
*[ 1 1 1 0 ]
—————-
= [ 1 1 1 1 ]
What if we treated these as numbers rather than vectors?
x
1
* 1 0 0 1 +
x
2
* 0 0 1 1 +
x
3
* 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
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
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