Technical reports:
Structure of Complexity Classes: Separations, Collapses, and Completeness
Lane A. Hemachandra
Downloads:
- Title:
- Structure of Complexity Classes: Separations, Collapses, and Completeness
- Author(s):
- Hemachandra, Lane A.
- Date:
- 1988
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:12024
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-343-88
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Abstract:
- 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.
- Subject(s):
- Computer science
- Item views:
- 45