ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Conflicting relativizations, also known as “Baker-Gill-Solovay phenomena,” are common place in complexity theory. However, Book, Long, and Selman (SIAM J. Comput.,13 (1984), 461–487) have shown thatP(A) = NP B (A) for all oraclesA if and only ifP = NP, whereNP B (A) denotes the class of languages accepted by nondeterministic machines which possess only a polynomial number of query strings in the computation tree. It is shown in this paper that any superpolynomial bound on the number of queries already yields the BGS phenomenon. Similar results hold for theNP = co-NP andNPC = NP questions. A second objective of this paper is to point out a technique of Hartmanis with which to achieve oracle constructions by using the Kolmogorov complexity. This relatively new technique seems to be adequate for obtaining separation results for complexity classes which are not enumerable.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01692055
Permalink