26 October - 1 November

 Week 4

• Oracles & The Polynomial Hierarchy: Oracles and oracle classes, Oracle worlds, The Polynomial Hierarchy, definition and properties. The complexity of optimization problems, the class FP^NP.
• The Structure of NP: Enumerations, Ladner’s Theorem.