The operators min and max on the polynomial hierarchy

DOI10.1142/S0129054100000181zbMATH Open1319.68095MaRDI QIDQ5249042FDOQ5249042

Authors: Harald Hempel, Gerd Wechsung 

Publication date: 29 April 2015

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

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

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)

Cites Work

• The complexity of optimization problems
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• The polynomial-time hierarchy
• The complexity of combinatorial problems with succinct input representation
• The complexity of facets (and some facets of complexity)
• 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
• Title not available (Why is that?)
• A complexity theory for feasible closure properties
• Generalizations of Opt P to the polynomial hierarchy
• Some observations on the connection between counting and recursion
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• Complexity classes of optimization functions

Cited In (11)

• Title not available (Why is that?)
• On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
• Generalizations of Opt P to the polynomial hierarchy
• Title not available (Why is that?)
• ON HIGHER ARTHUR-MERLIN CLASSES
• On the connection between interval size functions and path counting
• Title not available (Why is that?)
• Polynomial-time hierarchies on some classes of functions. I
• UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
• Title not available (Why is that?)
• 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)