Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-025 | 26th May 1997 00:00

The Operators min and max on the Polynomial Hierarchy


Authors: Harald Hempel, Gerd Wechsung
Publication: 17th June 1997 16:41
Downloads: 1190


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 characterized as max.NP) and that our definition sheds
new light on the classification of optimization functions.
We are able to show that the min and max classes are distinct under
reasonable structural assumptions. This is obtained by the study of the
interaction of the operators max and min with other well known operators
such as \exists, \forall, \parity, etc. Our work yields a variety of
characterizations of central complexity classes and allows us to define
the polynomial hierarchy uniformly by three operators.

ISSN 1433-8092 | Imprint