Loading...
Please wait, while we are loading the content...
Similar Documents
CONTROLLED RELATIVIZATIONS OF P AND NP % (Abstract) Ronald V. Book Department of Mathematics University of California at Santa Barbara Santa Barbara, California 93106, U.S.A
| Content Provider | Semantic Scholar |
|---|---|
| Author | Long, Timothy J. Selman, Alan L. |
| Abstract | Baker, Gill, and Solovay [1] argue on the basis of their relativization results that traditional methods, diagonalization in particular, will not settle questions such as "P =? NP" or "NP =? co-NP." On the one hand, ordinary diagonalization methods appear to be inadequate for showing P ~ NP since one might expect that such a method would apply equally well to all relativized classes so that for all A, P(A) ~ NP(A), contradicting the existence (shown in [i]) of a set B such that P(B) = NP(B). On the other hand, a general method for simulating nondeterministic machines by deterministic machines running in polynomial time should apply to relativized classes so that for all A, P(A) = NP(A), contradicting the existence (shown in [i]) of a set C such that P(C) # NP(C)° Much of the work on complexity-bounded reducibilities, their reduction classes, and relativizations of complexity classes has been carried out by researchers with backgrounds in recursive function theory. Thus, it has been natural to look for recursion theoretic arguments, that is, arguments that relativize. But the results of Baker, Gill, and Solovay (and many others) show that some questions about P-degrees of sets in |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://page-one.springer.com/pdf/preview/10.1007/BFb0036471 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
