THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY

DOI10.1142/S0129054100000181zbMath1319.68095MaRDI QIDQ5249042

Harald Hempel, Gerd Wechsung

Publication date: 29 April 2015

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

zbMATH Keywords

operatorscomputational complexitypolynomial hierarchyoptimization functions

Mathematics Subject Classification ID

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

Related Items (4)

UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS ⋮ On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ On the connection between interval size functions and path counting ⋮ ON HIGHER ARTHUR-MERLIN CLASSES

Cites Work

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

This page was built for publication: THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY