The Operators min and max on the Polynomial Hierarchy

摘要

Starting from Krentel's class OptP [Kre88] we define a general maximization operator max and a general minimization operator min for complexity classes and show that there are other interesting optimization classes beside OptP. We investigate the behavior of these operators on the polynomial hierarchy, in particular we study the inclusion structure of the classes max P, max NP, max coNP, min P, min NP and min coNP. Furthermore we prove some very powerful relations regarding the interaction of the operators max, min U, sig, C, direct+, and . Thsi gives us a tool to show that the considered min and max classes are distinct under reasonable structural assumptions. Besides that, we are able to characterize the polynomial hierarchy uniformly by three operators.