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?
SAT
Hamiltonian Cycle
General Knapsack
Maximum Independent Set
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.