The operators min and max on the polynomial hierarchy

DOI10.1142/S0129054100000181MaRDI QIDQ5249042zbMATH OpenFDO

Authors Harald Hempel, Gerd Wechsung

Publication date 29 April 2015

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054100000181

zbMATH Keywords

computational complexityoperatorspolynomial hierarchyoptimization functions

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The operators min and max on the polynomial hierarchy
• scientific article; zbMATH DE number 1390091
• The complexity of optimization problems
• Complexity classes of optimization functions
• Generalizations of Opt P to the polynomial hierarchy

Cites work

• scientific article; zbMATH DE number 809154 (Why is no real title available?)
• A complexity theory for feasible closure properties
• Complexity classes of optimization functions
• Generalizations of Opt P to the polynomial hierarchy
• More complicated questions about maxima and minima, and some closures of NP
• PP is as Hard as the Polynomial-Time Hierarchy
• Simple characterizations of \(P(\# P)\) and complete problems
• Some observations on the connection between counting and recursion
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• The Complexity of Enumeration and Reliability Problems
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The complexity of facets (and some facets of complexity)
• The complexity of optimization problems
• The polynomial-time hierarchy

Cited in

(12)

• scientific article; zbMATH DE number 6529183 (Why is no real title available?)
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• Generalizations of Opt P to the polynomial hierarchy
• scientific article; zbMATH DE number 1390091 (Why is no real title available?)
• ON HIGHER ARTHUR-MERLIN CLASSES
• On the connection between interval size functions and path counting
• scientific article; zbMATH DE number 5872208 (Why is no real title available?)
• Polynomial-time hierarchies on some classes of functions. I
• The operators min and max on the polynomial hierarchy
• UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
• scientific article; zbMATH DE number 3965441 (Why is no real title available?)
• Complexity classes of optimization functions

This page was built for publication: The operators min and max on the polynomial hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5249042)