01:198:344 Lecture 19: 2019-11-19 Design & Analysis of Algorithms
20 Nov 2019
School
Department
Course
Professor
2019-11-19 Design & Analysis of Algorithms
Complexity
- NP Complete vs P Problems
-
- What are P and NP?
- P: problems solvable in polynomial time
- NP: problems verifiable in polynomial time
- Reducing A to B
-
-
- If we reduce A to B we write A -> B
- If we could efficiently solve B, we could solve A
- If we know A cannot be efficiently solved then neither can B
- B is at least as hard as A
- Sometimes a reduction is written as A <=p B
-
-
- If A -> B and B -> C then A -> C
- Given (fAB, hAB) and (fBC, hBC) we can compose them:
- (fBC ∘ fAB, hAB ∘ hBC)
-
- NP Completeness
- A problem is NP Complete if:
- It’s in NP
- All other problems in NP reduce to it
- To show B is NP complete:
- Given an NP complete problem A
- Reduce A to B
-
-
- Ham, Path -> Ham. Cycle
- Is it easier to find a cycle than an (s, t) path?
-
-
- If a cycle is found
- Delete edges (t, x) and (x, s)
- If not
- Then there’s no path
- Contrapositive: (s, t) path -> cycle
- Independent Set -> Clique
