A Simple Proof of Toda's Theorem

by Lance Fortnow

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].