×
Jenner, Birgit; Torán, Jacobo

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

Theor. Comput. Sci. 141, No. 1-2, 175-193 (1995).
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)}}.\)

Cited in 21 Documents

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q45 Formal languages and automata
PDF BibTeX XML Cite
\textit{B. Jenner} and \textit{J. Torán}, Theor. Comput. Sci. 141, No. 1--2, 175--193 (1995; Zbl 0873.68058)
Full Text: DOI Link

References:

[1] Agarwal, M.; Arvind, V., Polynomial time truth-table reductions to p-selective sets, (Proc. 9th Structure in Complexity Theory Conference (1994)), 24-31
[2] Allender, E.; Wilson, C., Width-bounded reducibility and binary search over complexity classes, (Proc. 5th IEEE Structure in Complexity Theory Conference (1990)), 112-130
[4] Beigel, R., NP-hard sets are p-superterse unless \(R = NP \), (Tech. Report TR4 (1988), Dept. of Computer Science, John Hopkins University)
[5] Beigel, R.; Kummer, M.; Stephan, F., Approximable sets, (Proc. 9th Structure in Complexity Theory Conf. (1994)), 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, (Proc. 9th Structure in Complexity Theory Conf. (1994)), 43-53 · Zbl 0893.68069
[8] Buss, S. R.; Hay, L., On thruth-table reducibility to SAT and the difference hierarchy over NP, (Proc. 3rd IEEE Structure in Complexity Conf. (1988)), 224-233
[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 \(Θ_2^p\) and \(Δ_2^p\), (Proc. 9th STACS. Proc. 9th STACS, Lecture Notes in Computer Science, Vol. 577 (1992), Springer: Springer Berlin), 305-319 · Zbl 1494.68087
[12] Chandra, A. K.; Stockmeyer, L.; Vishkin, U., Constant depth reducibility, SIAM J. Comput., 13, 2, 423-439 (1984) · Zbl 0538.68038
[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, (Proc. 7th IEEE Structure in Complexity Theory Conf. (1992)), 107-110 · Zbl 0756.11042
[17] Fenner, S.; Homer, S.; Ogiwara, M.; Selman, A. L., On using oracles that compute values, (Proc. 10th STACS. Proc. 10th STACS, Lecture Notes in Computer Science, Vol. 665 (1993), Springer: Springer Berlin), 398-408 · Zbl 0799.68090
[18] Hemachandra, L., The sky is falling: The strong exponential hierarchy collapses, (Tech. Report TR86-777 (1986), Department of Computer Science, Cornell University)
[19] Jenner, B.; Kirsig, B.; Lange, K.-J., The logarithmic alternation hierarchy collapses \(AΣ_2^L = AΠ_2^L \), Inform. Comput., 1, 269-288 (1989) · Zbl 0668.68055
[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, (Proc. 2nd IEEE Structure in Complexity Theory Conf. (1987)), 33-40
[22] Kintala, C.; Fisher, P., Refining nondeterminism in relativized complexity classes, SIAM J. Comput., 13, 129-337 (1984)
[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: 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
[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, (Report LSI-7-93-R (1993), Universitat Politècnica de Catalunya: Universitat Politècnica de Catalunya Barcelona)
[31] Lozano, A.; Torán, J., On the non-uniform complexity of the graph isomorphism problem, (Proc. 7nd IEEE Structure in Complexity Theory Conf. (1992)), 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, (Proc. 9th Structure in Complexity Theory Conf. (1994)), 2-12
[34] Papadimitriou, C.; Yannakakis, M., On limited nondeterminism and the complexity of the VC-dimension, (Proc. 8th IEEE Structure in Complexity Theory Conf. (1993)), 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., (Proc. 8th Structure in Complexity Conference (1993)), personal communication
[38] Thierauf, T.; Toda, S.; Watanabe, O., On sets bounded truth-table reducible to P-selective sets, (Proc. 11th STACS Conf.. Proc. 11th STACS Conf., Lecture Notes in Computer Science, Vol. 775 (1994), Springer: Springer Berlin), 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.