More complicated questions about maxima and minima, and some closures of NP. (English) Zbl 0653.03027

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 C. H. Papadimitriou and 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.


03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity


Zbl 0571.68028
Full Text: DOI


[1] Cai, J.; Hemachandra, L., The Boolean hierarchy: hardware over NP, (Proc. Struct. in Compl. Theory Conf.. Proc. Struct. in Compl. Theory Conf., Lecture Notes in Computer Science, 223 (1986), Springer: Springer Berlin), 105-124 · Zbl 0611.68018
[2] Cai, J.; Meyer, G. E., Graph minimal uncolorability is \(D^P\)-complete, SIAM J. Comput. (1986), to appear. · Zbl 0626.05017
[3] Garey, M. R.; Johnson, D. S., Computers and Intractibility: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[4] Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120
[5] Hausdorff, F., Grundzüge der Mengenlehre (1914), Leipzig · JFM 45.0123.01
[6] Johnson, D. S., The NP-completeness column: an ongoing guide 15th edition, J. Algorithms, 6, 291-305 (1985) · Zbl 0588.68020
[7] Köbler, J., Die Differenz- und die truth-table-Hierarchie für NP, (Diploma thesis (1985), University of Stuttgart)
[8] Köbler, J.; Schöning, U.; Wagner, K. W., The difference and truth-table hierarchies for NP, Seminar für Informatik, EWH Koblenz (1986), also: RAIRO Inform. Théoriq. to appear.
[9] Ladner, R. E.; Lynch, N. A., Relativizations of questions about log-space computability, Math. Systems Theory, 10, 19-32 (1976) · Zbl 0341.68036
[10] Ladner, R. E.; Lynch, N. A.; Selman, A. L., A comparison of polynomial time reducibilities, Theoret. Comput. Sci., 1, 103-123 (1975) · Zbl 0321.68039
[11] Machtey, M.; Young, P., An Introduction to General Theory of Algorithms (1978), North-Holland: North-Holland New York · Zbl 0376.68027
[12] Papadimitriou, C. H., On the complexity of unique solutions, J. ACM, 31, 392-400 (1984) · Zbl 0631.68038
[13] Papadimitriou, C. H.; Wolfe, D., The complexity of facets resolved, Proc. 26th Ann. Symp. on Found. of Comp. Sci., 74-78 (1985)
[14] Papadimitriou, C. H.; Yannakakis, M., The complexity of facets (and some facets of complexity), Proc. 14th STOC. Proc. 14th STOC, J. Comput. System Sci., 28, 244-259 (1984) · Zbl 0571.68028
[15] Stockmeyer, L. J.; Meyer, A. R., Word problems requiring exponential time, Proc. 5th STOC, 1-9 (1973) · Zbl 0359.68050
[16] Stockmeyer, L. J., The polynomial-time hierarchy, Theoret. Comput. Sci., 3, 1-22 (1977) · Zbl 0353.02024
[17] Wagner, K.; Wechsung, G., Computational Complexity (1986), Verlag der Wissenschaften: Verlag der Wissenschaften Berlin, and Reidel, Dordrecht, 1986 · Zbl 0584.68061
[18] Wagner, K., On ω-regular sets, Inform. and Control, 43, 123-177 (1979) · Zbl 0434.68061
[19] Wagner, K., Compact descriptions and the counting polynomial-time hierarchy, Proc. 2nd Frege Conf.. Proc. 2nd Frege Conf., The complexity of combinatorial problems with succinct input representation. Proc. 2nd Frege Conf.. Proc. 2nd Frege Conf., The complexity of combinatorial problems with succinct input representation, Acta Inform., 23, 325-356 (1986) · Zbl 0621.68032
[20] Wagner, K., The complexity of graphs with regularities, (Proc. 11th MFCS Conf.. Proc. 11th MFCS Conf., Lecture Notes in Computer Science, 176 (1984), Springer: Springer Berlin), 544-552 · Zbl 0548.68039
[21] Wechsung, G.; Wagner, K. W., On the Boolean closure of NP, (Proc. FCT Conf. 1985. Proc. FCT Conf. 1985, Lecture Notes in Computer Science, 199 (1985), Springer: Springer Berlin), 485-493, Manuscript (extended abstract) as: G. Wechsung, On the Boolean closure of NP · Zbl 0581.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.