zbMATH — the first resource for mathematics

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
Full Text: DOI
[1] Cai, J.; Hemachandra, L., The Boolean hierarchy: hardware over NP, (), 105-124
[2] Cai, J.; Meyer, G.E., Graph minimal uncolorability is DP-complete, SIAM J. comput., (1986), to appear.
[3] Garey, M.R.; Johnson, D.S., Computers and intractibility: A guide to the theory of NP-completeness, (1979), Freeman San Francisco
[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, ()
[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 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, 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 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., The complexity of combinatorial problems with succinct input representation, Acta inform., 23, 325-356, (1986)
[20] Wagner, K., The complexity of graphs with regularities, (), 544-552
[21] Wechsung, G.; Wagner, K.W., On the Boolean closure of NP, (), 485-493, Manuscript (extended abstract) as: G. Wechsung, On the Boolean closure of NP
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.