Structure of Complexity Classes: Separations, Collapses, and Completeness
Lane A. Hemachandra
- Structure of Complexity Classes: Separations, Collapses, and Completeness
- Hemachandra, Lane A.
- Technical reports
- Computer Science
- Permanent URL:
- Columbia University Computer Science Technical Reports
- Part Number:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- 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.
- Computer science
- Item views: