More complicated questions about maxima and minima, and some closures of NP (Q1107524): Difference between revisions

Starting from NP-complete problems defined by questions of the kind `max...\(\geq m?'\) and `min...\(\leq m?'\) we consider problems defined by more complicated questions about these maxima and minima, as for example `max...\(=m?'\), `min...\(\in M?'\) and `is max...odd?'. This continues a work started by \textit{C. H. Papadimitriou} and \textit{M. Yannakakis} [J. Comput. Syst. Sci. 28, 244-259 (1984; Zbl 0571.68028)]. It is shown that these and other problems are complete in certain subclasses of the Boolean closure of NP and other classes in the interesting area below the class \(\Delta^ p_ 2\) of the polynomial-time hierarchy. Special methods are developed to prove such completeness results. For this it is necessary to establish some properties of the classes in question which might be interesting in their own right.