Relativized isomorphisms of NP-complete sets |
| |
Authors: | Judy Goldsmith Deborah Joseph |
| |
Affiliation: | (1) Department of Computer Science, University of Manitoba, R3T 2N2 Winnipeg, Manitoba, CANADA;(2) Department of Computer Sciences, University of Wisconsin-Madison, 53706 Madison, WI, USA;(3) Present address: Department of Computer Science, University of Kentucky, 40506-0027 Lexington, KY |
| |
Abstract: | In this paper, we present several results about collapsing and non-collapsing degrees ofNP-complete sets. The first, a relativized collapsing result, is interesting because it is the strongest known constructive approximation to a relativization of Berman and Hartmanis' 1977 conjecture that all mP-complete sets forNP arep-isomorphic. In addition, the collapsing result explores new territory in oracle construction, particularly in combining overlapping and apparently incompatible coding and diagonalizing techniques. We also present non-collapsing results, which are notable for their technical simplicity, and which rely on no unproven assumptions such as one-way functions. The basic technique developed in these non-collapsing constructions is surprisingly robust, and can be combined with many different oracle constructions. |
| |
Keywords: | complexity classes isomorphisms NP-completeness collapsing degrees relativized computation sparse oracles |
本文献已被 SpringerLink 等数据库收录! |
|