The operators min and max on the polynomial hierarchy

DOI10.1007/BFb0023451zbMath1499.68126MaRDI QIDQ5047162

Harald Hempel, Gerd Wechsung

Publication date: 9 November 2022

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A note on unambiguous function classes

Cites Work

• The complexity of computing the permanent
• 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
• On counting and approximation
• Generalizations of Opt P to the polynomial hierarchy
• The complexity of selecting maximal solutions
• Complexity classes of optimization functions
• A complexity theory for feasible closure properties
• The Complexity of Enumeration and Reliability Problems
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item