EECS 3101
Week 11 - Wednesday
Ilir Dema
1
Intractability
2
P = NP ?
3
What do P and NP mean?
• P: Set of all decision problems solvable
in polynomial time on a deterministic
Turing machine
• e.g., Is the shortest path between u and v in
a graph shorter than k?
• The set of all decision problems solvable in
polynomial time on REAL computers.
• NP: Set of all decision problems solvable
in polynomial time on a
nondeterministic Turing machine.
• Set of all decision problems with efficient
(polynomial-time) verification algorithms
4
NP-Hard and NP-Complete
• NP-Hard (informally)
• A problem with the property that if it can
be solved efficiently, then it can be used as
a subroutine to solve any other problem in
NP efficiently.
• NP-Complete
• Problems that are both NP and NP-hard.
• “Hardest computational problems” in NP
5
P = NP?
• If we find a polynomial-time solution to
any NP-Complete problem, then P = NP.
• If we can find any problem that is in NP
but not in P, then P ≠ NP.
• First asked in 1971 (Cook and Levine)
• $1,000,000 prize by Clay Mathematics
Institute if you can do either of the above.
6
NP-Complete Problems
• The hardest problems in NP.
• We haven’t found polynomial-time solutions for these problem.
• Best we can do so far is exponential-time solutions.
• We also haven’t been able to prove that a polynomial-time solution
doesn’t exist.
• What we want to learn: be able to identify the NP-Completeness of a given
problem, so that you can
• avoid wasting time on finding an accurate polynomial solution
• re-examine the problem to see how likely the worst-case occurs
• find alternatives such as approximation/heuristic algorithms
• keep trying, prove P = NP, and win a million dollar.
7
NP-Complete Problem
Examples
8
The Satisfiability Problem (SAT)
• Given a Boolean formula written in a canonical conjunction-of-
disjunctions form, decide if there exists a set of values of x1, x2,.., xn
that make the expression evaluate TRUE.
• This is called 2-SAT since each
disjunction has two literals.
• It’s proven to be in P.
• This is called 3-SAT since each
disjunction has three literals.
• It’s proven to be NP-Complete.
9
Travelling Salesman Problem (TSP)
• A traveling salesperson needs
to visit n cities.
• Is there a route of at most d
length? (decision problem)
• Optimization version:
• find a shortest cycle visiting all
vertices once in a weighted
graph
• Related: finding the longest-
path on a weighted graph is
also NP-Complete.
Image source: https://www.math.uwaterloo.ca/tsp/poke/index.html
10
CLIQUE
• Given an undirected graph with n
vertices, is there a subset (of size s)
of vertices such that all pairs of
vertices in the subset are adjacent
to each other.
• Optimization versions:
• find a list of maximal cliques
• find the maximum clique
11
How to Identify an
NP-Complete Problem?
12
Reduction
• If we know problem B can be solved by solving an instance of
problem A, i.e., A is “harder” than B, then we say, “B reduces to A”.
• If we can find an algorithm that reduces problem B to problem A in
polynomial time, and we know that B is NP-complete.
• then we can conclude that A is NP-Complete.
13
Reduction Example
• SAT reduces to CLIQUE
• Given any input of a SAT problem, we
convert it to an input of a CLQUE problem.
• Specifically, for a SAT formula with K
disjunctions, we construct a CLIQUE input
that has a clique of size K if and only if the
original Boolean formula is satisfiable.
14
Reduction Example
Conclusion:
• SAT reduces to CLIQUE
• SAT is known to be NP-Complete
• then CLIQUE must be NP-Complete
15
Approximation Algorithms
16
Approximation Algorithms
• Once we know a problem is NP-Complete, we understand it’ll be
quite unrealistic to find a polynomial-time solution that returns the
optimal solution.
• An alternative to design an algorithm that gets an “approximately
optimal” solution.
• sometimes, we can prove “how close” it is to the real optimal solution
17
Example: Travelling Salesman Problem
• An approximation algorithm
• Find the MST of the graph
• Traverse the vertices according
to the preorder-traversal of the
MST (close the cycle by going
back to the root at the end).
• The resulting trip is guaranteed
to be at most 2x the length of
the real optimal solution
(assuming triangle inequality
holds)
• This algorithm is called a 2-
approxmation algorithm. approx. solution real optimal solution
18
Summary
• We’re only scratching the surface of the theory of computational
complexity and computability.
• If this fascinates you, learn more in EECS 4111 or EECS 4115.
19
Next
• Wrap-up and exam review!
20
