\(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


Zbl 0493.68043
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, (Proceedings, 3rd Structure in Complexity Theory Conference (1988)), 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] R. Chang, 1988, private communication.; R. 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?, (Technical Report TR 86-795 (December 1986), Cornell Department of Computer Science)
[9] Hemachandra, L. A., The strong exponential hierarchy collapses, (Proceedings, 19th ACM Symposium on Theory of Computing (1987)), 110-122 · Zbl 0693.03022
[10] Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: 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, (Technical Report TR 86-771 (August 1986), Cornell Department of Computer Science)
[13] Kadin, J., \(p^{NP}\)[log \(n]\) and sparse Turing complete sets for NP, (Proceedings, 2nd Structure in Complexity Theory Conference (1987)), 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) · Zbl 0631.68038
[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, (Sixth GI Conference on Theoretical Computer Science. Sixth GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 145 (1983), Springer-Verlag: Springer-Verlag New York/Berlin), 269-275 · Zbl 0506.68039
[23] Stockmeyer, L., The Complexity of Decision Problems in Automata Theory and Logic, (Technical Report MAC TR-133 (1974), MIT), 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, (Proceedings, 13th International Colloquium on Automata, Languages, and Programming (ICALP). Proceedings, 13th International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, Vol. 226 (1986), Springer-Verlag: Springer-Verlag New York/ Berlin), 434-443 · Zbl 0629.68049
[26] Wagner, K., Bounded Query Classes, (Technical Report 157 (October 1987), University of Augsburg) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.