Lecture 39 -04/26

Impossible and Intractible Problems, Problem Complexity, NP Completeness

Kolmogorov Complexity

Difficulty of Problems

Sidenote: The Independent Set Problem

Sidenote: Reductions

Complexity Classes

Completeness

P = NP?