×

A taxonomy of complexity classes of functions. (English) Zbl 0806.68049

Summary: This paper comprises a systematic comparison of several complexity classes of functions that are computed nondeterministically in polynomial time or with an oracle in NP. There are three components to this work:
\(\bullet\) A taxonomy is presented that demonstrates all known inclusion relations of these classes. For (nearly) each inclusion that is not shown to hold, evidence is presented to indicate that the inclusion is false. As an example, consider FewPF, the class of multivalued functions that are nondeterministically computable in polynomial time such that for each \(x\) there is a polynomial bound on the number of distinct output values of \(f(x)\). We show that \(\text{FewPF} \subseteq_ c \text{PF}^{\text{NP}}_{tt}\). However, we show \(\text{PF}^{\text{NP}}_{tt} \subseteq \text{FewPF}\) if and only if \(\text{NP} = \text{co-NP}\), and thus \(\text{PF}^{\text{NP}}_{tt} \subseteq \text{FewPF}\) is likely to be false.
\(\bullet\) Whereas it is known that \(\text{P}^{\text{NP}}(O (\log n)) = \text{P}^{\text{NP}}_{tt} \subseteq \text{P}^{\text{NP}}\), we show that \(\text{PF}^{\text{NP}}(O(\log n)) = \text{PF}^{\text{NP}}_{tt}\) implies \(P = \text{FewP}\) and R = NP. Also, we show that \(PF^{\text{NP}}_{tt} = \text{PF}^{\text{NP}}\) if and only if \(P^{\text{NP}}_{tt} = \text{P}^{\text{NP}}\).
\(\bullet\) We show that if every nondeterministic polynomial-time multivalued function has a single-valued nondeterministic refinement (equivalently, if every honest function that is computable in polynomial- time can be inverted by a single-valued nondeterministic function), then there exists a disjoint pair of NP-complete sets such that every separator is NP-hard. The latter is a previously studied open problem that is closely related to investigations on promise problems. This result motivates a study of reductions between partial multivalued functions.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allender, E.; Rubinstein, R., P-printable sets, SIAM J. Comput., 17, No. 6, 1193-1202 (1988) · Zbl 0682.68039
[2] Beigel, R., NP-Hard Sets Are P-Superterse Unless R = NP, (Technical Report 88-04 (1988), Department of Computer Science, The Johns Hopkins University: Department of Computer Science, The Johns Hopkins University San Mateo, CA)
[3] Buss, S.; Hay, L., On truth table reducibility to sat and the difference hierarchy over NP, (Proceedings, 3rd IEEE Conference on Structure in Complexity Theory (1988)), 224-233
[4] Beigel, R.; Hemachandra, L.; Wechsung, G., On the power of probabilistic polynomial time, (Proceedings, 4th IEEE Conference on Structure in Complexity Theory (1989)), 225-227
[5] Book, R.; Long, T.; Selman, A., Quantitative relativations of complexity classes, SIAM J. Comp., 13, No. 3, 461-487 (1984) · Zbl 0599.03041
[6] Cai, J.; Hemachandra, L., On the power of parity polynomial time, Math. Systems Theory, 23, No.2, 95-106 (1990) · Zbl 0718.68038
[7] Cook, S., The complexity of theorem-proving procedures, (Proceedings, 3rd ACM Symp. Theory of Computing (1971)), 151-158
[8] Even, S.; Selman, A.; Yacobi, Y., The complexity of promise problems with applications to public-key cryptography, Inform. and Control, 61, No. 2, 159-173 (1984) · Zbl 0592.94012
[9] Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 168-198 (1981) · Zbl 0539.90078
[10] Grollmann, J.; Selman, A., Complexity measures for public-key cryptosystems, SIAM J. Comput., 17, No. 2 (1988) · Zbl 0644.94016
[11] Hemachandra, L., Counting in Structural Complexity Theory, (Ph.D. thesis (1987), Cornell University)
[12] Kadin, J., \(P^{NP}\)[log \(n]\) and sparse Turing-complete sets for NP, (Proceedings, 2nd IEEE Conference on Structure in Complexity (1987)), 33-40
[13] Krentel, M., The complexity of optimization problems, J. Comput. Systems Sci., 36, 490-509 (1988) · Zbl 0652.68040
[14] Köbler, J.; Schöning, U.; Wagner, K., The difference and truth-table hierarchies for NP, RAIRO Theoretical Informatics and Applications, 21, No. 4, 419-435 (1987) · Zbl 0642.03024
[15] Selman, A., Polynomial time enumeration reducibility, SIAM J. Comput., 7, No. 4, 440-457 (1978) · Zbl 0386.68055
[16] Selman, A., Natural self-reducible sets, SIAM J. Comput., 17, 989-996 (1988) · Zbl 0665.68030
[17] Selman, A., A survey of one-way functions in complexity theory, Math. Systems Theory, 25, 203-221 (1992) · Zbl 0749.68037
[18] Selman, A.; Xu, M.-R.; Book, R., Positive relativizations of complexity classes, SIAM J. Comput., 12, 465-479 (1983)
[19] Toda, S., On the computational power of PP and ⊕P, (Proceedings, 30th IEEE Symp. on Foundations of Computer Science (1989)), 514-519
[20] Toda, S., On polynomial-time truth-table reducibilities of intractable sets to P-selective sets, Math. Systems Theory, 24, No. 2, 69-82 (1991) · Zbl 0722.68059
[21] Valiant, L., Relative complexity of checking and evaluating, Inform. Process. Lett., 5, No. 1, 20-23 (1976) · Zbl 0342.68028
[22] Valiant, L.; Vazirani, V., NP is as easy as detecting unique solutions, (Proceedings 17th ACM Symp. Theory of Computing (1985)), 458-463 · Zbl 0621.68030
[23] Wagner, K., Bounded Query Classes, (Technical Report TR-157 (1987), Universität Augsburg, Institut für Mathematik) · Zbl 0711.68047
[24] Wagner, K., Log Query Classes, (Technical Report TR-145 (1987), Universität Augsburg, Institut für Mathematik)
[25] Watanabe, O.; Toda, S., Structural analysis of the complexity of inverse functions, Math. Systems Theory, 26, No. 2, 203-214 (1993) · Zbl 0771.68070
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.