期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
