Introduction to NP Completeness

An introduction to NP Completeness

1. 1
NP-Completeness
November 28, 2003
Young Eun Kim and Gene Moo Lee
Department of Computer Science & Engineering
Korea University

2. 2/30
Contents
•Introduction and Motivation
•Background Knowledge
•Definition of NP-Completeness
•Examples of NP-Complete Problems
•Hierarchy of Problems
•How to Prove NP-Completeness
•How to Cope with NP-Complete Problems
•Conclusion

3. 3/30
Introduction (1/2)
•Some Algorithms we’ve seen in this class
–Sorting – O(N log N)
–Searching – O(log N)
–Shortest Path Finding – O(N
2
)
•However, some problems only have
–Exponential Time Algorithm O(2
N
)
–So What?
Why? What? How?

4. 4/30
Introduction (2/2)
N 10 20 30 40 50 60
O(N)
.00001
second
.00002
second
.00003
second
.00004
second
.00005
second
.00006
second
O(N
2
)
.0001
second
.0004
second
.0009
second
.0016
second
.0025
second
.0036
second
O(N
3
)
.001
second
.008
second
.027
second
.064
second
.125
second
.216
second
O(N
5
)
1
second
3.2
seconds
24.3
seconds
1.7
minutes
5.2
minutes
13.0
minutes
O(2
N
)
.001
second
1.0
second
17.9
minutes
12.7
days
35.7
years
366
centuries
O(3
N
)
.059
second
58
minutes
6.5
years
3855
centuries
2*10
8
centuries
10
13
centuries
Why? What? How?

5. 5/30
Motivation
•Traveling Salesman Problem (n = 1000)
•Compute 1000!
–Even Electron in the Universe is a Super Computer,
–And they work for the Estimated Life of the Universe,
–WE CANNOT SOLVE THIS PROBLEM!!!
–This kind of problems are NP-Complete.
Why? What? How?

6. 6/30
Background Knowledge
To understand NP-Completeness, need to
know these concepts
1.Decision and Optimization Problems
2.Turing Machine and class P
3.Nondeterminism and class NP
4.Polynomial Time Reduction
(Problem Transformation)
Why? What? How?

7. 7/30
Decision and Optimization Problems
•What is the Shortest Path from A to B?
–This is an Optimization Problem.
•Is there a Path from A to B consisting of at
most K edges?
–This is the related Decision Problem.
We consider only Decision Problems!
Why? What? How?

8. 8/30
Turing Machine and Class P
(1/3)
Church – Turing Thesis
“Computer ≡ Turing Machine”
Alan Turing(1912-1954)
(www.time.com)
Why? What? How?

9. 9/30
Turing Machine and Class P
(2/3)
A Turing machine
is a 7-tuple (Q, ∑, Γ, δ, q
0
, q
accept
, q
reject
).
Why? What? How?

10. 10/30
Turing Machine and Class P
(3/3)
P : the class of problems that are
decidable in polynomial time on a
Turing machine
Sorting, Shortest Path are in P!
Why? What? How?

11. 11/30
Nondeterminism and Class NP (1/2)
• A Nondeterministic Turing machine is a Turing
machine with the transition function has the form
δ : Q * Γ  P(Q * Γ * {L, R}).
• NTM guess to choose the answer nondeterministically
Why? What? How?

12. 12/30
Nondeterminism and Class NP (2/2)
•NP : the class of problems that are decidable in
polynomial time on a nondeterministic Turing
machine
•Solutions of problems in NP can be checked
(verified) in polynomial time.
•If a Hamiltonian path were discovered somehow,
we could easily check if the path is Hamiltonian.
–HAMPATH is in NP! Also Sorting is in NP!
Why? What? How?

13. 13/30
Class P and NP
•P = the class of problems where
membership can be decided quickly.
•NP = the class of problems where
membership can be verified quickly.
Why? What? How?

14. 14/30
Polynomial Time Reduction
Traveling Salesman Problem5-CliqueMap Coloring
Traveling Salesman Problem
 5-Clique  Map Coloring
Why? What? How?

15. 15/30
Definition of NP-Completeness
A problem B is NP-complete
if it satisfies two conditions:
1.B is in NP, and
2.Every problem A in NP is polynomial
time reducible to B. (NP-Hard)
Why? What? How?

16. 16/30
Meaning of NP-Completeness
•NP: Nondeterministic Polynomial
•Complete:
–If one of the problems in NPC have an
efficient algorithm, then all the problems
in NP have efficient algorithms.
Why? What? How?

17. 17/30
Examples of NP-Completeness
•Satisfiability (SAT)
•Traveling Salesman Problem (TSP)
•Longest Path (vs. Shortest Path is in P)
•Real-Time Scheduling
•Hamiltonian Path (vs. Euler Path is in P)
Why? What? How?

18. 18/30
Where are we?
Background Knowledge
Definition of NP-Completeness
Examples of NP-Complete Problems
•Hierarchy of Problems
•How to Prove NP-Completeness
•How to Cope with NP-Completeness

19. 19/30
Hierarchy of Problems (1/2)
P NP PSPACE = NPSPACE EXPTIME
⊆ ⊆ ⊆
Conjectured Relationships
EXPTIME
NPSPACE
NP P
UNDECIDABLE
Why? What? How?

20. 20/30
Hierarchy of Problems (2/2)

NP

P
Which one is correct?
An efficient algorithm on a
deterministic machine does not
exist.
An efficient algorithm on a
deterministic machine is not
found yet.
P = NP
Why? What? How?

21. 21/30
How to prove NP-Completeness(1/3)
•If B is NP-complete and B C for C in NP,
∝
then C is NP-complete.
B C

NP-complete NP-complete
Then, we need at least one NP-complete problem!
Why? What? How?

22. 22/30
How to prove NP-Completeness(2/3)
Cook’s Theorem
“Satisfiability Problem (SAT) is
NP-complete.”
- the first NP-complete
problem!
Stephen Cook
(www.cs.toronto.edu)
Why? What? How?

23. 23/30
I’m also NP
Complete!
How to prove NP-Completeness(3/3)
any NP
problem
can be reduced to...
SAT
new NP
problem
can be reduced to...
Proved by
Cook
New Problem
is “no easier”
than SAT
Why? What? How?

24. 24/30
NP-Complete Problems Tree
SAT
3-SAT
Graph 3-Color
3-DM
Exact Cover
Planer 3-color
Vertex Cover
Subset-Sum
HAMPATH
Clique
Partition
Integer
Programming
Independent
TSP (Salesman)
Why? What? How?

25. 25/30
How to Cope with NP-Completeness
I.HEURISTIC ALGORITHM
To find a solution within a reduced search-space.
II. APPROXIMATION ALGORITHM
To find approximately optimal solutions.
III. QUANTUM COMPUTING
To use the spins of quantum with the speed of
light. (bit 0, 1 spin-up (0), spin-down (1))
Why? What? How?

26. 26/30
Heuristic Algorithm
•In NP-Complete Problems,
we have to check exponential possibilities.
•By Heuristic, reduce the search space.
•Example: Practical SAT problem Solvers
–zChaff, BerkMin, GRASP, SATO, etc.
Why? What? How?

27. 27/30
Approximation
•Hard to find an exactly correct solution
in NP-complete problems
•By Approximation,
find a nearly optimal solution.
•Example: finding the smallest vertex covers
(we can find a vertex cover never more than
twice the size of the smallest one.)
Why? What? How?

28. 28/30
Quantum Computation
•Bit 0 and 1 
Spin Up and Spin
Down
•Speed of electron
 Speed of light
Why? What? How?
Digital Comp.  Quantum Comp.

29. 29/30
Conclusion
When a hard problem is given,
we can prove that a problem is NP-complete,
just by finding a polynomial time reduction.
After proving,
we can solve the problem in these ways:
Heuristic Algorithm, Approximation
Algorithm and Quantum computing.

30. 30/30
Thank You for Listening.
Any Question?