Announcements
Announcements
Exam 3 on Friday
Homework 5 Solutions online
Last Time
NP Decision/Optimization Problems
Decision: Does object with easily checkable property exist?
Optimization: What object maximizes/minimizes easily computation function?
SAT
Hamiltonian Cycle
It is believed that some NP problems are hard, but proving anything is very difficult.
Reduction A → B
Instance of
problem A
Instance of
problem B
Solution to problem B instance
Solution to problem A instance
Polynomial time reduction algorithm
Hypothetical algorithm for B
Polynomial time interpretation algorithm
Solution to A
Shows B is at least as hard as A
Today
NP-Completeness
3-SAT
Circuit SAT
Problem: Given a circuit C with several Boolean inputs and one Boolean output, determine if there is a set of inputs that give output 1.
x
y
z
out
Important Reduction:
Any NP decision problem → Circuit SAT
Any NP Decision Problem
→ Circuit SAT
Any NP decision problem asks if there is some X that satisfies a polynomial-time checkable property.
In other words, for some polynomial-time computable function F, it asks if there is an X so that F(X) = 1.
Create a circuit C that computes F. The problem is equivalent to asking if there is an input for which C outputs 1.
NP-Complete
Circuit-SAT is our first example of an
NP-Complete problem. That is a problem in NP that is at least as hard as any other problem in NP.
Good news: If we find a polynomial time algorithm for Circuit-SAT, we have a polynomial time algorithm for all NP problems!
Bad news: If any problem in NP is hard, Circuit-SAT is hard.
Note: Decision problems can be NP-Complete. For optimization problems, it is called NP-Hard.
Other NP-Complete/Hard Problems
The following are all NP-Complete/Hard:
Formula SAT
Maximum Independent Set
TSP
Hamiltonian Cycle
Knapsack
How do we show this? By finding reductions from other NP-Hard/Complete Problems.
3-SAT
3-SAT is a special case of formula-SAT where the formula is an AND of clauses and each clause is an OR of at most 3 variables or their negations.
Example:
Circuit-SAT → 3-SAT
Start with circuit
x
y
z
out
Create variable for each wire
Create formula with clause for each gate and output
w
v
u
t
These Aren’t 3-SAT Clauses
We have 3-variable clauses that aren’t 3-SAT clauses. Write it in terms of them.
Write truth table
Each 3-SAT clause sets one output to false.
X
X
X
X
Note
This means that 3-SAT is also NP-Complete since we have:
Any problem in NP → Circuit SAT → 3-SAT
What other problems can we show to be
NP-Complete/NP-Hard this way?
Another Look at 3-SAT
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.
Example:
Proof
If satisfiable:
Satisfying assignment causes at least one term in each clause to be true.
Select one such term from each clause.
Cannot contradict each other.
Example:
Proof
If there is a way to select terms:
Set those variables to be true
Can do this without contradiction
Set other variables arbitrarily
Causes whole statement to be true
Example:
3-SAT → Maximum Independent Set
Want to encode this select one term from each clause as a graph.
Create one vertex for each term in each clause.
Edges between terms in same clause.
Edges between contradictory terms.
Example:
x
y
z
x̄
y
y̅
x̄
Analysis
An independent set in this graph has:
At most one vertex from each clause.
No vertices representing contradictory terms.
It has an independent set of size #Clauses if and only if, you can select one term form each clause without a contradiction.
Therefore, |MIS| = #Clauses if and only if the 3-SAT has a solution.
Example
x
y
z
x̄
y
y̅
x̄
Intermediate Problems
To prove our more complicated reductions, it will help to have the correct problem to prove reductions from.
A convenient problem is the one the book calls Zero-One Equations.
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.
This problem is clearly in NP. We will show that it is NP-Complete.
Example
Equivalently, do there exist x1, x2, x3 ∈ {0,1} so that
x1+x3 = 1
x1+x2 = 1
Generally, this is what a ZoE looks like. A bunch of sets of xis that need to add to 1.