zbMATH — the first resource for mathematics

\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP. (English) Zbl 0693.68027
It has been known (S. Mahaney [J. Comput. Syst. Sci. 25, 130-143 (1987; Zbl 0493.68043)] that the polynomial hierarchy collapses to \(P^{NP}\) if NP has a \(\leq^ P_ T\)-complete sparse set. The author improves this result by replacing \(N^{NP}\) with \(P^{NP[O(\log n)]}\), where this latter class is the class of all languages acceptable by deterministic polynomial time machines making only O(log n) queries to an NP-oracle. This result is a consequence of the following one: If for a sparse S in NP it holds that \(coNP\subseteq NP^ S\), then \(PH\subseteq P^{NP[O(\log n)]}\). This collapse result is optimal in the following sense: For any function \(f(n)=o(\log n)\) there exists a set B for which \(NP^ B\) has a sparse \(\leq^ P_ T\)-complete set and \((P^ B)^{NP^ B[O(\log n)]}\subseteq (P^ B)^{NP^ B[f(n)]}.\)
Furthermore, the paper exhibits \(\leq^ P_ m\)-complete problems for \(P^{NP[O(\log n)]}\) and discusses conditions fo the class of languages \(\leq^ P_ m\)-reducible to a set C to be equal to \(P^{C[O(\log n)]}\). For \(D^ P=\{X\cap Y :\) \(X\in NP\wedge Y\in coNP\}\) it is shown: If \(D^ P=coD^ P\), then \(P^{NP[O(\log n)]}\subseteq D^ P\).
Reviewer: G.Wechsung

68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D10 Turing machines and related notions
68Q45 Formal languages and automata
Full Text: DOI
[1] Beigel, R., Bounded queries to SAT and the Boolean hierarchy, Theoret. comput. sci., (1988), in press
[2] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. comput., 6, No. 2, 305-322, (1977) · Zbl 0356.68059
[3] Blass, A.; Gurevich, Y., On the unique satisfiability problem, Inform. and control, 55, 80-88, (1982) · Zbl 0543.03027
[4] Buss, S.; Hay, L., On truth-table reducibility to SAT and the difference hierarchy over NP, (), 224-233
[5] Cai, J.; Gundermann, T.; Hartmanis, J.; Hemachandra, L.; Sewelson, V.; Wagner, K.; Wechsung, G., The Boolean hierarchy I. structural properties, SIAM J. comput., 17, (1988) · Zbl 0676.68011
[6] {\scR. Chang}, 1988, private communication.
[7] Heller, H., On relativized exponential and probabilistic complexity classes, Inform. and control, 71, 231-243, (1986) · Zbl 0628.68047
[8] Hemachandra, L.A., Can P and NP manufacture randomness?, ()
[9] Hemachandra, L.A., The strong exponential hierarchy collapses, (), 110-122 · Zbl 0693.03022
[10] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[11] Immerman, N.; Mahaney, S., Relativizing relativized computations, Theoret. comput. sci., (1988) · Zbl 0679.68084
[12] Kadin, J., Deterministic polynomial time with O(log n) queries, ()
[13] Kadin, J., P^{NP}[logn] and sparse Turing complete sets for NP, (), 33-40
[14] Kadin, J., The polynomial hierarchy collapses if the Boolean hierarchy collapses, SIAM J comput., 17, (1988) · Zbl 0664.03031
[15] Karp, R.; Lipton, R., Turing machines that take advice, Enseign. math., 28, 191-209, (1982) · Zbl 0529.68025
[16] Krentel, M., The complexity of optimization problems, J. comput. system sci., 36, 490-509, (1988) · Zbl 0652.68040
[17] Ladner, R.; Lynch, N.; Selman, A., A comparison of polynomial time reducibilities, Theoret. comput. sci., 1, No. 2, 103-124, (1975) · Zbl 0321.68039
[18] Long, T., A note on sparse oracles for NP, J. comput. system sci., 24, 224-232, (1982) · Zbl 0486.68033
[19] Mahaney, S., Sparse complete sets for NP: solution of a conjecture of berman and hartmanis, J. comput. system sci., 25, No. 2, 130-143, (1982) · Zbl 0493.68043
[20] Papadimitriou, C., On the complexity of unique solutions, J. assoc. comput. Mach., 31, No. 2, 392-400, (1984)
[21] Papadimitriou, C.; Yannakakis, M., The complexity of facets (and some facets of complexity), J. comput. system sci., 28, No. 2, 244-259, (1984) · Zbl 0571.68028
[22] Papadimitriou, C.; Zachos, S., Two remarks on the power of counting, (), 269-275
[23] Stockmeyer, L., The complexity of decision problems in automata theory and logic, (), Project MAC
[24] Stockmeyer, L., The polynomial-time hierarchy, Theoret. comput. sci., 3, 1-22, (1977) · Zbl 0353.02024
[25] Wagner, K., More complicated questions about maxima and minima, and some closures of NP, (), 434-443
[26] Wagner, K., Bounded query classes, () · Zbl 0711.68047
[27] Wilson, C., Relativized circuit complexity, J. comput. system sci., 31, No. 2, 169-181, (1985) · Zbl 0583.68023
[28] Yap, C., Some consequences of non-uniform conditions on uniform classes, Theoret. comput. sci., 26, 287-300, (1983) · Zbl 0541.68017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.