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