Complexity classes of optimization functions

DOI10.1006/INCO.1995.1109MaRDI QIDQ1898460zbMATH OpenOpenAlexFDO

Authors Heribert Vollmer, K. W. Wagner

Publication date 16 April 1996

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/35b34374eef8b25ac764d9d01bbff8d129cc5fe7

zbMATH Keywords

\(p\)-founded class of optimization functionscomplexity classes

Mathematics Subject Classification ID

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

Recommendations

• The operators min and max on the polynomial hierarchy
• The operators min and max on the polynomial hierarchy
• Polynomial-time hierarchies on some classes of functions. I
• Continuous optimization problems and a polynomial hierarchy of real functions
• scientific article; zbMATH DE number 1390091

Cited in

(14)

• Polynomial-time hierarchies on some classes of functions. I
• Recursion theoretic characterizations of complexity classes of counting functions
• Optimal satisfiability for propositional calculi and constraint satisfaction problems.
• A note on unambiguous function classes
• Lower bound on complexity of optimization of continuous functions
• Weighted Boolean formula games
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• scientific article; zbMATH DE number 1136092 (Why is no real title available?)
• UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
• On the complexity of inverse mixed integer linear optimization
• The operators min and max on the polynomial hierarchy
• The operators min and max on the polynomial hierarchy
• ON HIGHER ARTHUR-MERLIN CLASSES
• A note on the depth function of combinatorial optimization problems

This page was built for publication: Complexity classes of optimization functions

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