On the Structure of Sets in NP and Other Complexity Classes
Loading...
Files
Date
Authors
Landweber, Lawrence
Lipton, Richard
Robertson, Edward
Advisors
License
DOI
Type
Technical Report
Journal Title
Journal ISSN
Volume Title
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Grantor
Abstract
A simple technique is developed for manipulating the relative complexity of sets with respect to polynomial time reducibility. One application is the definition of a minimal pair (with respect to polynomial time reducibility) of sets in NP-P. The last section proves that the NP-complete are effectively enumerable while NP-P is not.
Description
Keywords
Related Material and Data
Citation
TR342