NP Completeness (CLRS, Ch. 34)

• Course Introduction.
• Syllabus.
• Problem classes: undecidable, intrinsically exponential, intractable, polynomial.
• Abstract problems and decision problems. Reduction from optimization to decision problems. Example: SHORTEST UNWEIGHTED PATH.