Day 13

We talked about the three definitions of the polynomial-time hierarchy, by oracles, alternation and quantification, and the basic properties.

• The equivalence problem for regular expressions with squaring requires exponential space by Albert Meyer and Larry Stockmeyer. This is the paper that first defined the polynomial-time hierarchy. 
• The wikipedia article on the polynomial-time hierarchy goes through all three definitions and the basic relationships.
• Completeness in the Polynomial-Time Hierarchy by Marcus Schaefer and Chris Umans. A compendium of problems complete for various higher levels of the hierarchy.