Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes. (English) Zbl 0733.68031
The concept of a nonuniform proof system, as a generalization of Karp/Lipton’s advice classes, is introduced and studied. Many results from (nonuniform) complexity theory can thus be obtained in a unified framework. This includes certain results on probabilistic classes, lowness results, and collapsing results for the polynomial-time hierarchy.
Reviewer: U.Schöning (Ulm)
MSC:
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
References:
| [1] | Abadi, M.; Feigenbaum, J.; Kilian, J., On hiding information from an oracle, Proc. 19th ACM STOC, 195-203 (1987) |
| [2] | Babai, L., Trading group theory for randomness, Proc. 17th ACM STOC, 421-429 (1985) |
| [3] | Babai, L., Arthur-Merlin games: a randomized proof system and a short hierarchy of complexity classes (1986), manuscript |
| [4] | Balcázar, J. L.; Book, R. V.; Schöning, U., Sparse oracles, lowness, and highness, (Proc. 11th Internat. Symp. Math. Foundations of Comput. Sci.. Proc. 11th Internat. Symp. Math. Foundations of Comput. Sci., Lecture Notes in Computer Science, Vol. 176 (1984), Springer: Springer Berlin), 185-193 · Zbl 0554.68033 |
| [5] | Balcázar, J. L., Self-reducibility, (Proc. 4th STAC. Proc. 4th STAC, Lecture Notes in Computer Science, Vol. 247 (1986), Springer: Springer Berlin), 136-147 · Zbl 0628.68048 |
| [6] | Balcázar, J. L.; Book, R. V.; Schöning, U., Sparse sets, lowness, and highness, SIAM J. Comput., 15, 739-747 (1986) · Zbl 0621.68033 |
| [7] | Balcázar, J. L.; Diaz, J.; Gabarro, J., Structural Complexity I, (EATCS Monographs on Theor. Comput. Sci., Vol. 11 (1988), Springer: Springer Berlin) · Zbl 0574.68039 |
| [8] | Chandra, A. K.; Kozen, D. C.; Stockmeyer, L. J., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043 |
| [9] | Gill, J., Computational complexity of probabilistic complexity classes, SIAM J. Comput., 6, 675-695 (1977) · Zbl 0366.02024 |
| [10] | Kämper, J., Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes, 3/87 (1987), Universität Oldenburg, Bericht · Zbl 0733.68031 |
| [11] | Karp, R. M.; Lipton, R. J., Some connections between nonuniform and uniform complexity classes, Proc. 12th ACM STOC, 302-309 (1980) |
| [12] | Ko, K., On self-reducibility and weak p-selectivity, J. Comput. System Sci., 26, 209-221 (1983) · Zbl 0519.68062 |
| [13] | Ko, K., Some observations on the probabilistic algorithms and NP-hard problems, Inform. Process Lett., 14, 39-43 (1983) · Zbl 0483.68045 |
| [14] | Ko, K.; Schöning, U., On circuit-size complexity and the low hierarchy in NP, SIAM J. Comput., 14, 41-51 (1985) · Zbl 0562.68033 |
| [15] | Ko, K., On helping by robust oracle machines, Proc. Structure in Complexity Theory Conf., 182-190 (1987) · Zbl 0635.68039 |
| [16] | Lautemann, C., BPP and the polynomial hierarchy, Inform. Process Lett., 14, 215-217 (1983) · Zbl 0515.68042 |
| [17] | Long, T. J., Strong nondeterministic polynomial-time reducibilities, Theoret. Comput. Sci., 21, 1-25 (1982) · Zbl 0521.03028 |
| [18] | Meyer, A.; Paterson, M., With what frequency are apparently intractable problems difficult?, (MIT/LCS/TM-126 (1979), Lab. for Computer Science, MIT: Lab. for Computer Science, MIT Cambridge, Massachusetts) |
| [19] | Pippenger, N., On simultaneous resource bounds, Proc. 20th IEEE Symp. Foundations of Computer Science, 307-311 (1979) |
| [20] | Schöning, U., A low and a high hierarchy within NP, J. Comput. System Sci., 27, 14-28 (1983) · Zbl 0515.68046 |
| [21] | Schöning, U., On small generators, Theoret. Comput. Sci., 34, 337-341 (1984) · Zbl 0558.68040 |
| [22] | Schöning, U., Netzwerkkomplexität, probabilistische Algorithmen und Relativierungen, (Habilitationsschrift (1985), Universität Stuttgart) · Zbl 0575.68050 |
| [23] | Schöning, U., Complexity and structure, (Lecture Notes in Computer Science, Vol. 211 (1986), Springer: Springer Berlin) · Zbl 0872.68048 |
| [24] | Schöning, U., Graph isomorphism is in the low hierarchy, (Proc. 4th STACS. Proc. 4th STACS, Lecture Notes in Computer Science, Vol. 247 (1986), Springer: Springer Berlin), 114-124 · Zbl 0621.68034 |
| [25] | Schöning, U., Probabilistic complexity classes and lowness, Proc. Structure in Complexity Theory Conf., 2-8 (1987) |
| [26] | Selman, A. L., P-SELECTIVE sets, tally languages, and the behaviour of polynomial-time reducibilities on NP, Math. Systems Theory, 13, 55-65 (1979) · Zbl 0405.03018 |
| [27] | Selman, A. L., Reductions on NP and P-SELECTIVE sets, Theoret. Comput. Sci., 19, 287-304 (1982) · Zbl 0489.03016 |
| [28] | Sipser, M., A complexity theoretic approach to randomness, Proc. 15th ACM STOC, 330-335 (1983) |
| [29] | Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024 |
| [30] | Yap, C. K., Some consequences of nonuniform conditions on uniform classes, Theoret. Comput. Sci., 26, 287-300 (1983) · Zbl 0541.68017 |
| [31] | Yesha, Y., On certain polynomial-time truth-table reducibilities of complete sets to sparse sets, SIAM J. Comput., 12, 411-425 (1983) · Zbl 0545.03023 |
| [32] | Zachos, S., Probabilistic quantifiers, adversaries, and complexity classes, (Proc. Structure in Complexity Theory Conf.. Proc. Structure in Complexity Theory Conf., Lecture Notes in Computer Science, Vol. 223 (1986), Springer: Springer Berlin), 383-400 · Zbl 0632.03035 |
| [33] | Zachos, S.; Heller, H., A decisive characterization of BPP, Inform. and Control, 69, 125-135 (1986) · Zbl 0616.68049 |
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.
