Computing functions with parallel queries to NP. (English) Zbl 0873.68058

Summary: The class \(\Theta ^{p}_{2}\) of languages polynomial-time truth-table reducible to sets in NP has a wide range of different characterizations. We consider several functional versions of \(\Theta ^{p}_{2}\) based on these characterizations. We show that in this way the three function classes FL\(^{\text{NP}}_{\log}\), FP\(^{\text{NP}}_{\log}\), and FP\(^{\text{NP}}_{\parallel}\) are obtained. In contrast to the language case the function classes seem to all be different. We give evidence in support of this fact by showing that FL\(^{\text{NP}}_{\log}\) coincides with any of the other classes then L=P, and that the equality of the classes FP\(^{\text{NP}}_{\log}\) and FP\(^{\text{NP}}_{\parallel}\) would imply that the number of nondeterministic bits needed for the computation of any problem in NP can be reduced by a polylogarithmic factor, and that the problem can be computed deterministically with a subexponential time bound of order \(2^{n^{O(1/\log \log n)}}.\)


68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q45 Formal languages and automata
Full Text: DOI Link


[1] Agarwal, M.; Arvind, V., Polynomial time truth-table reductions to p-selective sets, (), 24-31
[2] Allender, E.; Wilson, C., Width-bounded reducibility and binary search over complexity classes, (), 112-130
[3] a journal version is to appear as: Adaptive logspace reducibiity and parallel time, Math. Systems Theory. · Zbl 0773.68028
[4] Beigel, R., NP-hard sets are p-superterse unless R = NP, ()
[5] Beigel, R.; Kummer, M.; Stephan, F., Approximable sets, (), 12-24
[6] Blass, A.; Gurevich, Y., On the unique satisfiability problem, Inform. control, 55, 80-88, (1982) · Zbl 0543.03027
[7] Buhrman, H.; Kadin, J.; Thierauf, T., On functions computable with nonadaptive queries to NP, (), 43-53 · Zbl 0893.68069
[8] Buss, S.R.; Hay, L., On thruth-table reducibility to SAT and the difference hierarchy over NP, (), 224-233
[9] S.R. Buss, J. Krajicek and G. Takeuti, Provably total functions in bounded arithmetic theories R3i, U2i and V2i, in: P. Clote and J. Krajicek, eds., Arithmetic, Proof Theory and Computational Complexity (Oxford University Press, Oxford) to appear.
[10] Cai, J.; Hemachandra, L., Enumerative counting is hard, Inform. comput., 82, 34-44, (1989) · Zbl 0679.68072
[11] Castro, J.; Seara, C., Characterizations of some complexity classes between θ2p and δ2p, (), 305-319
[12] Chandra, A.K.; Stockmeyer, L.; Vishkin, U., Constant depth reducibility, SIAM J. comput., 13, 2, 423-439, (1984) · Zbl 0538.68038
[13] Z.Z. Chen and S. Toda, On the complexity of computing the minimum subgraph, submitted.
[14] Díaz, J.; Torán, J., Classes of bounded nondeterminism, Math. systems theory, 23, 21-32, (1990) · Zbl 0692.68029
[15] Even, S.; Selman, A.; Yacobi, Y., The complexity of promise problems with applications to public-key cryptography, Inform. control, 61, 114-133, (1984)
[16] Fellows, M.R.; Koblitz, N., Self-witnessing polynomial-time complexity and prime factorization, (), 107-110
[17] Fenner, S.; Homer, S.; Ogiwara, M.; Selman, A.L., On using oracles that compute values, (), 398-408 · Zbl 0799.68090
[18] Hemachandra, L., The sky is falling: the strong exponential hierarchy collapses, ()
[19] Jenner, B.; Kirsig, B.; Lange, K.-J., The logarithmic alternation hierarchy collapses 2L = Aπ2L, Inform. comput., 1, 269-288, (1989)
[20] Johnson, D.S., Approximation algorithms for combinatorial problems, J. comput. systems sci., 9, 3, 256-278, (1974) · Zbl 0296.65036
[21] Kadin, J., P^{NP[log]} and sparse Turing-complete sets for NP, (), 33-40
[22] Kintala, C.; Fisher, P., Refining nondeterminism in relativized complexity classes, SIAM J. comput., 13, 129-337, (1984)
[23] J. Köbler, personal communication, Ulm, 1991.
[24] Köbler, J.; Schöning, U.; Torán, J., On counting and approximation, Acta informatica, 26, 363-379, (1989) · Zbl 0663.03025
[25] Köbler, J.; Schöning, U.; Torán, J., the graph isomorphism problem, its structural complexity, (1993), Birkhauser Basel · Zbl 0813.68103
[26] Krentel, M.V., The complexity of optimization problems, J. comput. system sci., 36, 490-509, (1988) · Zbl 0652.68040
[27] R.E. Ladner, The circuit value problem is log space complete for P.SIGACT NEWS{\bf7}, pp. 18-20.
[28] Ladner, R.E.; Lynch, N., Relativization of questions about log space computability, Math. systems theory, 10, 19-32, (1976) · Zbl 0341.68036
[29] Ladner, R.E.; Lynch, N.; Selman, A., Comparison of polynomial-time reducibilities, Theoret. comput. sci., 1, 103-123, (1975) · Zbl 0321.68039
[30] Lozano, T., Parallel versus logarithmic many queries to NP, ()
[31] Lozano, A.; Torán, J., On the non-uniform complexity of the graph isomorphism problem, (), 118-131
[32] Mathon, R., A note on the graph isomorphism counting problem, Inform. process. lett., 8, 131-312, (1979) · Zbl 0395.68057
[33] Ogiwara, M., Polynomial-time membership comparable sets, (), 2-12
[34] Papadimitriou, C.; Yannakakis, M., On limited nondeterminism and the complexity of the VC-dimension, (), 12-19
[35] Selman, A.L., A taxonomy of complexity classes of functions, J. comput. system sci., 48, 2, 357-381, (1994) · Zbl 0806.68049
[36] Selman, A.; Mei-Rui, X.; Book, R., Positive relativizations of complexity classes, SIAM J. comput., 12, 565-579, (1983) · Zbl 0551.68043
[37] Thierauf, T., (), personal communication
[38] Thierauf, T.; Toda, S.; Watanabe, O., On sets bounded truth-table reducible to P-selective sets, (), 427-438 · Zbl 0941.03541
[39] Toda, S., On polynomial-time truth-reducibilities of intractable sets to P-selective sets, Math. systems theory, 24, 2, 69-82, (1991) · Zbl 0722.68059
[40] Valiant, L., The complexity of computing the permanent, Theoret. comput. sci., 8, 189-201, (1979) · Zbl 0415.68008
[41] Valiant, L.; Vazirani, V., NP is as easy as detecting unique solutions, Theoret. comput. sci., 47, 85-93, (1986) · Zbl 0621.68030
[42] Wagner, K.W., Bounded query classes, SIAM J. comput., 19, 5, 833-846, (1990) · Zbl 0711.68047
[43] Wilson, C., Decomposing AC and NC, SIAM J. comput., 19, 2, 384-396, (1990) · Zbl 0692.68045
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.