Home

Structure of Complexity Classes: Separations, Collapses, and Completeness

Lane A. Hemachandra; Columbia University. Computer Science

Title:
Structure of Complexity Classes: Separations, Collapses, and Completeness
Author(s):
Hemachandra, Lane A.; Columbia University. Computer Science
Date:
Type:
Technical reports
Department:
Computer Science
Permanent URL:
Series:
Columbia University Computer Science Technical Reports
Part Number:
CUCS-343-88
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:
55
Metadata:
text | xml

In Partnership with the Center for Digital Research and Scholarship at Columbia University Libraries/Information Services | Terms of Use