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
1. Transform an instance of uniqueness to an instance of CP (in this case, no transformation needed)
2. Solve the CP instance
3. 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:
1. X is in NP
2. 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

• Terminology due to Knuth