×

Bounded queries to SAT and the Boolean hierarchy. (English) Zbl 0739.68035

Summary: We study the complexity of decision problems that can be solved by a polynomial-time Turing machine that makes a bounded number of queries to an \(NP\) oracle. Depending on whether we allow some queries to depend on the results of other queries, we obtain two (probably) different hierarchies. We present several results relating the bounded \(NP\) query hierarchies to each other and to the Boolean hierarchy. We also consider the similarly defined hierarchies of functions that can be computed by a polynomial-time Turing machine that makes a bounded number of queries to an \(NP\) oracle. We present relations among these two hierarchies and the Boolean hierarchy. In particular we show for all \(k\) that there are functions computable with \(2^ k\) parallel queries to an \(NP\) set that are not computable in polynomial time with \(k\) serial queries to any oracle, unless \(P=NP\). As a corollary \(k+1\) parallel queries to an \(NP\) set allow us to compute more functions than are computable with only \(k\) parallel queries to an \(NP\) set, unless \(P=NP\); the same is true of serial queries. Similar results hold for all \(tt\)-self-reducible sets.
Using a “mind-change” technique, we show that \(2^ k-1\) parallel queries to an \(NP\) set allow us to accept in polynomial time exactly the same sets as can be accepted in polynomial time with \(k\) serial queries to an \(NP\) set. (In fact, the same is true for any class in place of \(NP\) that is closed under polynomial-time positive-bounded-truth-table reductions.) This contrasts with the expected result for function computation with an \(NP\) oracle R. Beigel [\(NP\)-hard sets are \(P\)- superterse unless \(R=NP\), TR 4, Dept. of Computer Science, The Johns Hopkins University (1988)].
In addition we show that the Boolean hierarchy and the bounded query hierarchies (of languages) either stand or collapse together. Finally we show that if the Boolean hierarchy collapses to any level but the zeroth (deterministic polynomial time), then for all \(k\) there are functions computable in polynomial time with \(k\) parallel queries to an \(NP\) set that are not computable in polynomial time with \(k-1\) serial queries to any set (\(NP\)-complete sets are \(p\) superterse).

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amir, A.; Beigel, R.; Gasarch, W. I., Some connections between bounded query classes and non-uniform complexity, (Proc. 5th Ann. Conf. on Structure in Complexity Theory (1990), IEEE Computer Soc. Press: IEEE Computer Soc. Press Silver Spring, MD), 232-243
[2] Amir, A.; Gasarch, W. I., Polynomial terse sets, Inform. and Comput., 77, 37-56 (1988) · Zbl 0646.68049
[3] Balcázar, J. L.; Díaz, J.; Gabarró, J., Structural complexity I, EATCS Monogr. Theoret. Comput. Sci., 11 (1988) · Zbl 0638.68040
[4] Beigel, R., Bi-immunity results for cheatable sets, Theoret. Comput. Sci., 73, 249-263 (1990) · Zbl 0709.03032
[5] Beigel, R., NP-hard sets are p-superterse unless R = NP, (Tech. Report 4 (1988), Dept. of Computer Science, The Johns Hopkins University)
[6] Beigel, R., Query-limited reducibilities, (Ph.D. Thesis (1987), Stanford University)
[7] Beigel, R., A structural theorem that depends quantitatively on the complexity of SAT, (Proc. 2nd Ann. Conf. on Structure in Complexity Theory (1987), IEEE Computer Soc. Press), 28-34
[8] Beigel, R., When are \(k + 1\) queries better than \(k\)?, (Tech. Report 6 (1988), Dept. of Computer Science, The Johns Hopkins University)
[11] Book, R. V.; Ko, K.-I., On sets truth-table reducible to sparse sets, SIAM J. Comput., 17, 903-919 (1988) · Zbl 0665.68040
[12] Buss, S. R.; Hay, L. E., On truth table reducibility to SAT and the difference hierarchy over NP, (Proc. 3rd Ann. Conf. on Structure in Complexity Theory (1988), IEEE Computer Soc. Press), 224-233
[13] Cai, J., On some most probable separations of complexity classes, (Ph.D. Thesis (1986), Cornell University: Cornell University Ithaka, NY)
[14] Cai, J.; Hemachandra, L. A., The Boolean hierarchy: hardware over NP, (Structure in Complexity Theory. Structure in Complexity Theory, Lecture Notes in Computer Science, Vol. 223 (1986), Springer: Springer Berlin), 105-124
[15] Goldsmith, J.; Joseph, D.; Young, P., Using self-reducibilities to characterize polynomial time, (Tech. Report 87-11-11 (1987), Dept. of Computer Science, Univ. of Washington: Dept. of Computer Science, Univ. of Washington Seattle), to appear in Inform. and Comput. · Zbl 0776.68044
[16] Hemachandra, L. A., The strong exponential hierarchy collapses, Proc. 19th Ann. ACM Symp. on Theory of Computing (1987) · Zbl 0693.03022
[17] Köbler, J.; Schöning, U.; Wagner, K. W., The difference and truth-table hierarchies for NP, RAIRO Inform. Théor. Appl., 21, 419-435 (1987) · Zbl 0642.03024
[18] Krentel, M. W., The complexity of optimization problems, J. Comput. System Sci., 36, 3, 490-509 (1988) · Zbl 0652.68040
[19] Markov, A. A., On the inversion complexity of a system of functions, J. Assoc. Comput. Mach., 6, 331-334 (1958) · Zbl 0085.11601
[20] Meyer, A.; Paterson, M., With what frequency are apparently intractable problems difficult?, (Tech. Report MIT/LCS/TM-126 (1979), M.I.T)
[21] Owings, J. C., A cardinality version of Beigel’s Nonspeedup Theorem, J. Symbolic Logic, 54, 3, 761-767 (1989) · Zbl 0685.03034
[22] Papadimitriou, C. H.; Yannakakis, M., The complexity of facets (and some facets of complexity), J. Comput. System Sci., 28, 244-259 (1984) · Zbl 0571.68028
[23] Papadimitriou, C. H.; Zachos, S. K., Two remarks on the complexity of counting, (Proc. 6th GI Conf. of Theoretical Computer Science. Proc. 6th GI Conf. of Theoretical Computer Science, Lecture Notes in Computer Science, Vol. 145 (1983), Springer: Springer Berlin), 269-276
[24] Putnam, H., Trial and error predicates and the solution to a problem of Mostowski, J. Symbolic Logic, 30, 1, 49-57 (1965) · Zbl 0193.30102
[25] Russo, D. A., Structural properties of complexity classes, (Ph.D. Thesis (March 1985), Univ. of California: Univ. of California Santa Barbara)
[26] Schnorr, C. P., Optimal algorithms for self-reducible problems, Proc. 3rd Internat. Coll. on Automata, Languages, and Programming, 322-337 (1976)
[27] Schöning, U.; Wagner, K. W., Collapsing oracle hierarchies, census functions, and logarithmically many queries, (Tech. Report 140 (1987), Institut für Mathematik, Universität Augsburg) · Zbl 0648.68065
[28] Wagner, K. W., Bounded query classes, (Tech. Report 157 (1987), Institut für Mathematik, Universität Augsburg) · Zbl 0711.68047
[29] Wechsung, G.; Wagner, K., On the Boolean closure of NP, (Proc. 1985 Internat. Conf. on Fundamentals of Computation Theory. Proc. 1985 Internat. Conf. on Fundamentals of Computation Theory, Lecture Notes in Computer Science, Vol. 199 (1985), Springer: Springer Berlin), 485-493
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.