Announcements
Announcements
• Exam 3 on Friday
NP-Completeness (Ch 8)
• NP-Problems
• Reductions
• NP-Completeness & NP-Hardness
• SAT
• Hamiltonian Cycle
• Zero-One Equations
• Knapsack
Brute Force Algorithms
For almost every problem we have seen there
has been a (usually bad) naïve algorithm that
just considers every possible answer and
returns the best one.
• Is there a path from s to t in G?
• What is the longest common subsequence?
• What is the closest pair of points?
• Does G have a topological ordering?
NP
Such problems are said to be in Nondeterministic
Polynomial time (NP).
NP-Decision problems ask if there is some object that
satisfies a polynomial time-checkable property.
NP-Optimization problems ask for the object that
maximizes (or minimizes) some polynomial time-
computable objective.
Optimization vs. Decision
Note that these are not too different.
• Every decision problem can be phrased as an
optimization problem (objective has value 1 if
the object satisfies the condition and 0
otherwise).
• Every optimization problem has a decision
form (can we find an example whose objective
is more than x).
Examples of NP Problems
• SAT
• TSP
• Hamiltonian Cycle
• Knapsack
• Maximum Independent Set
SAT
Problem: Formula-SAT
Given a logical formula in a number of Boolean
variables, is there an assignment to the
variables that causes the formula to be true?
Applications of SAT
• Circuit Design
• Logic Puzzles
• Cryptanalysis
Hamiltonian Cycle (in text as
Rudruta Path)
Given an undirected graph G is there a cycle that
visits every vertex exactly once?
General Knapsack
Recall knapsack has a number of items each
with a weight and a value. The goal is to find
the set of items whose total value is as much
as possible without the total weight going
exceeding some capacity.
Have algorithm that runs in polynomial time
in the weights.
If weights are allowed to be large (written in
binary), don’t have a good algorithm.
Question: Decision vs.
Optimization
Which of the following are NP-Decision
problems?
A) SAT
B) Hamiltonian Cycle
C) General Knapsack
D) Maximum Independent Set
E) Travelling Salesman
Brute Force Search
• Every NP problem has a brute force search
algorithm.
• Throughout this class we have looked at
problems with algorithms that substantially
improve on brute force search.
• Does every NP problem have a better-than-
brute-force algorithm?
P vs. NP
$1,000,000 Question: Is P = NP?
Is it the case that every problem in NP has a
polynomial time algorithm?
• If yes, every NP problem has a reasonably
efficient solution.
• If not, some NP problems are fundamentally
difficult
Most computer scientists believe P ≠ NP.
(But proving anything is very very hard)
Hard Problems
In practice, at least some problems in NP appear
to be hard. Despite decades of trying, people
still don’t know particularly good algorithms.
So if you have a problem, how do you know if it
is hard or not?
• Can search for algorithms (to show it’s easy).
• Can try to prove that it is hard, but this is
extremely difficult.
• Can try to relate its difficulty to that of other
problems.
Reductions
Reductions are a method for proving that one
problem is at least as hard as another.
How do we do this?
We show that if there is an algorithm for solving
A, then we can use this algorithm to solve B.
Therefore, B is no harder than A.
Hamiltonian Cycle → TSP
Hamiltonian
Cycle Instance TSP Instance
Cost = 1
Cost = 2
Formally
• Given Ham. Cycle Instance G
• Create TSP Instance H
– Edges in G are cost 1
– Edges not in G are cost 2
• Solve TSP instance
– Have a cycle of cost |V| in H if and only if
Hamiltonian cycle in G
• Use answer to solve initial problem
If, we have an
algorithm that solves
TSP, we can use it to
solve Ham. Cycle.
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
Create H with edge
weights 1 and 2
See if solution has
weight |V|
Reduction A → B
If we have algorithms for reduction and
interpretation:
• Given an algorithm to solve B, we can turn it
into an algorithm to solve A.
• This means that A might be easier to solve
than B, but cannot be harder.