HomeHome

Structure of Complexity Classes: Separations, Collapses, and Completeness

Lane A. Hemachandra

Title:
Structure of Complexity Classes: Separations, Collapses, and Completeness
Author(s):
Hemachandra, Lane A.
Date:
Type:
Technical reports
Department(s):
Computer Science
Persistent URL:
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
100
Metadata:
text | xml
Suggested Citation:
Lane A. Hemachandra, , Structure of Complexity Classes: Separations, Collapses, and Completeness, Columbia University Academic Commons, .

Columbia University Libraries | Policies | FAQ