×

A note on the circuit complexity of PP. (English) Zbl 1080.68041

Summary: We show that for any integer \(k\), there are languages in the complexity class PP that do not have Boolean circuits of size \(n^{k}\).

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Aaronson, Oracles are subtle but not malicious, Technical Report TR05-040, Electronic Colloq. on Computational Complexity, 2005, available at \(\&\#60;>\); S. Aaronson, Oracles are subtle but not malicious, Technical Report TR05-040, Electronic Colloq. on Computational Complexity, 2005, available at \(\&\#60;>\)
[2] Arvind, V.; Köbler, J.; Schöning, U.; Schuler, R., If NP has polynomial-size circuits then \(\operatorname{MA} = \operatorname{AM} \), Theoret. Comput. Sci., 137, 2, 279-282 (1995) · Zbl 0874.68185
[3] L. Babai, Trading group theory for randomness, in: Proc. of the 17th ACM Symp. on Theory of Computing, 1985, pp. 421-429.; L. Babai, Trading group theory for randomness, in: Proc. of the 17th ACM Symp. on Theory of Computing, 1985, pp. 421-429.
[4] Babai, L.; Fortnow, L., Arithmetization: a new method in structural complexity theory, Comput. Complexity, 1, 41-66 (1991) · Zbl 0774.68040
[5] Balcázar, J.; Díaz, J.; Gabarró, J., Structural Complexity—I & II (1988), Springer: Springer Berlin
[6] Beigel, R., Perceptrons, PP, and the polynomial hierarchy, Comput. Complexity, 4, 4, 339-349 (1994) · Zbl 0829.68059
[7] J.-Y. Cai. \( \operatorname{S}_2^{\operatorname{P}} \subsete; \operatorname{ZPP}^{\operatorname{NP}} \); J.-Y. Cai. \( \operatorname{S}_2^{\operatorname{P}} \subsete; \operatorname{ZPP}^{\operatorname{NP}} \)
[8] Gill, J., Computational complexity of probabilistic complexity classes, SIAM J. Comput., 6, 675-695 (1977) · Zbl 0366.02024
[9] Kannan, R., Circuit-size lower bounds and non-reducibility to sparse sets, Inform. Control, 55, 40-56 (1982) · Zbl 0537.94027
[10] R. Karp, R. Lipton, Some connections between uniform and non-uniform complexity classes, in: Proc. of the 12th Ann. ACM Symp. on Theory of Computing, 1980, pp. 302-309.; R. Karp, R. Lipton, Some connections between uniform and non-uniform complexity classes, in: Proc. of the 12th Ann. ACM Symp. on Theory of Computing, 1980, pp. 302-309.
[11] Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N., Algebraic methods for interactive proof systems, J. ACM, 39, 4, 859-868 (1992) · Zbl 0799.68097
[12] Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0833.68049
[13] Schöning, U., Probabilistic complexity classes and lowness, J. Comput. System Sci., 39, 84-100 (1988) · Zbl 0688.68045
[14] Toda, S.; Ogiwara, M., Counting classes are at least as hard as the polynomial-time hierarchy, SIAM J. Comput., 21, 2, 316-328 (1992) · Zbl 0755.68055
[15] Vereshchagin, N. K., On the power of PP, (Proc. of the 7th IEEE Annu. Conf. on Structure in Complexity Theory (1992), Boston: Boston MA, USA), 138-143
[16] Wilson, C. B., Reltivized circuit complexity, J. Comput. System Sci., 31, 2, 169-181 (1985) · Zbl 0583.68023
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.