THE OPERATORS MIN AND MAX ON THE POLYNOMIAL HIERARCHY
From MaRDI portal
Publication:5249042
DOI10.1142/S0129054100000181zbMath1319.68095MaRDI QIDQ5249042
Publication date: 29 April 2015
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
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