Extension of Toda's Theorem to Middle Bit Classes (Survey)
Johannes Köbler
Abstract:
In this paper we overview recent results concerning complexity classes that are defined in terms of the number of accepting paths of nondeterministic polynomial-time Turing machines. Of central interest are Toda's celebrated results showing the hardness of several counting classes for the polynomial-time hierarchy. Furthermore, we review the more recent progress that has been made in extending Toda's Theorem to middle bit classes, and we briefly describe how this work has been applied in circuit complexity to establish improved simulations of the class ACC.
Ps-File: Extension of Toda's Theorem to Middle Bit Classes