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

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Motivated by the question of how to define an analog of interactive

proofs in the setting of logarithmic time- and space-bounded

computation, we study complexity classes defined in terms of

operators quantifying over oracles. We obtain new

characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ...
more >>>

Elmar Böhler, Christian Glaßer, Daniel Meister

SBP is a probabilistic promise class located

between MA and AM \cap BPPpath. The first

part of the paper studies the question of whether

SBP has many-one complete sets. We relate

this question to the existence of uniform

enumerations. We construct an oracle relative to

which SBP and AM do ...
more >>>