NP-Completeness
Topics
- This is a very simplified introduction to P and NP
- Reduction
- Class P
- Class NP
- Cook's Theorem: All problems in NP reduce to SAT
- NP-Complete: Problem X is NPC if X is in NP and all NP reduces to X
- SAT reduces to other problems
- NP-Complete
- NP-Hard
NP-Completeness
Reduction
- Example: Uniqueness reduces to Closest pair
- Transform an instance of uniqueness to an instance of CP (in this case, no transformation needed)
- Solve the CP instance
- Transform the CP result to a Uniqueness result
- If A transforms to B, then A is the same or faster complexity
- Write as A → B
- Question: If one is harder, is it A or B? Answer: B
Problems in P
- Problems in P: can be solved in Polynomial Time
- that is, known to have polynomial time solutions
- Examples: edit distance, shortest path, MST
- Question: Are all problems in P known: no
Problems in NP
- Problems in NP: solutions can be checked in Polynomial Time
- Example: partition set of integers into 2 subsets with equal sums
- NP means Nondeterministic Polynomial: a nondeterministic algorithm guesses a solution that is checked in
polynomial time (itec 420)
- Question: Are all problems in NP known: no
Cook's Theorem and Problem SAT
- Problem SAT: Is a boolean expression in a certain form satisfiable?
- Satisfiable = can it be made true
- Example 1: (w OR z) AND (x OR y' OR z) AND (x' OR y') is satisfiable (with TTFT)
- Example 2: (w OR x OR y OR z) AND (w' OR x' OR y' OR z') is NOT satisfiable
- Cooks Theorem: All problems in NP are reducible to SAT!
- Not proved by transforming all NP problems to SAT (all are not known!)
Consequences of Cook's Theorem
- If a polynomial time solution to SAT is found, all NP problems have a polynomial time solution
- SAT in P implies P = NP
There's More
- SAT itself can be reduced to many other problems in NP
- If any of these problems are solved, then all are solved and P=NP
"Solve"
- We informally say "solve" to mean find a polynomial time solution
NP-Complete
- A problem X is NP-Complete if these hold:
- X is in NP
- Every problem in NP reduces to X
- What are some NP-Complete problems:
- SAT (proved by Cook)
- Any problem P such that SAT (or any other NPC problem) reduces to P
Consequences of being NP-Complete
- Solving any NP-Complete problem would solve all NP problems
- Solving any NP-Complete problem would prove P=NP (one million dollar prize)
- NP-Complete problems are the hardest problems in NP
- If you know a problem is NPC, then you know that you will probably not be able to find an efficient
algorithm for it
Proving a problem is NP-Complete
- To show that problem X is NPC, show the following:
- X is in NP (ie checkable in poly time)
- Every problem in NP reduces to X
- Show this by showing that some (other) NPC problem reduces to X
NP-Hard
- A problem P is NP-Hard if every problem in NP reduces to P
- Alternatively, problem P is NP-Hard if some NP-Complete reduces to P
Consequences of NP-Hard
- Solving a NP-Hard problem ... does what?
- Solving an NP-Complete problem says what about the NP-Hard problem
A Final Note on Terminology