Harald Hempel, Gerd Wechsung

We define a general maximization operator max and a general minimization

operator min for complexity classes and study the inclusion structure of

the classes max.P, max.NP, max.coNP, min.P, min.NP, and min.coNP.

It turns out that Krentel's class OptP fits naturally into this frame-

work (it can be ...
more >>>

Martin Sauerhoff

One of the great challenges of complexity theory is the problem of

analyzing the dependence of the complexity of Boolean functions on the

resources nondeterminism and randomness. So far, this problem could be

solved only for very few models of computation. For so-called

partitioned binary decision diagrams, which are a ...
more >>>

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>