A Simple Proof of Toda's Theorem
Theory of Computing, Volume 5(7), pp. 135-140, 2009
Bibliography with links to cited articles
[1] S. Aaronson: The complexity zoo. http://complexityzoo.com.
[2] S. Arora and B. Barak: Complexity Theory: A Modern Approach. Cambridge University Press, Cambridge, 2009.
[3] S. Fenner, L. Fortnow, and S. Kurtz: Gap-definable counting classes. J. Comput. System Sci., 48(1):116–148, 1994. [doi:10.1016/S0022-0000(05)80024-8].
[4] L. Fortnow: Counting complexity. In L. Hemaspaandra and A. Selman, editors, Complexity Theory Retrospective II, pp. 81–107. Springer, 1997.
[5] L. Fortnow: Making pigs fly. Computational Complexity Weblog, June 2006. http://weblog.fortnow.com/2005/06/making-pigs-fly.html.
[6] C. Papadimitriou and S. Zachos: Two remarks on the power of counting. In Proc. 6th GI-Conf. Theor. Comput. Sci., volume 145 of LNCS, pp. 269–276. Springer, Berlin, 1983. [doi:10.1007/BFb0009651].
[7] S. Toda: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. [doi:10.1137/0220053].
[8] L. Valiant and V. Vazirani: NP is as easy as detecting unique solutions. Theoret. Comput. Sci., 47:85–93, 1986. [doi:10.1016/0304-3975(86)90135-0].
[9] S. Zachos: Probabilistic quantifiers and games. J. Comput. System Sci., 36(3):433–451, 1988. [doi:10.1016/0022-0000(88)90037-2].