1988 Reports

Structure of Complexity Classes: Separations, Collapses, and Completeness

Hemachandra, Lane A.

During the last few years, unprecedented programs has been made in structural complexity theory; class inclusions and relativised separations were discovered, and hierarchies collapsed. We survey this progress, highlighting the central role of counting techniques. We also present a new result whose proof demonstrate the power of combinational arguments: there is a relativezed world in which UP has no Turing complete sets.