UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS

DOI10.1142/S0129054100000326MaRDI QIDQ4528761zbMATH OpenOpenAlexFDO

Authors Sven Kosub, H. Schmitz, Heribert Vollmer

Publication date 20 May 2001

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

Full work available at URL https://doi.org/10.1142/s0129054100000326

zbMATH Keywords

function classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1136092
• A uniform approach to define complexity classes
• A taxonomy of complexity classes of functions
• Recursion theoretic characterizations of complexity classes of counting functions
• scientific article; zbMATH DE number 2040949

Cites work

• A note on unambiguous function classes
• A taxonomy of complexity classes of functions
• A uniform approach to define complexity classes
• Complexity classes of optimization functions
• Computing functions with parallel queries to NP
• Gap-definable counting classes
• Gap-languages and log-time complexity classes
• Generalizations of Opt P to the polynomial hierarchy
• Logspace and logtime leaf languages
• On the acceptance power of regular languages
• PP is as Hard as the Polynomial-Time Hierarchy
• Quantitative Relativizations of Complexity Classes
• Succinct circuit representations and leaf language classes are basically the same concept
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• THE COMPLEXITY OF FINDING MIDDLE ELEMENTS
• The complexity of optimization problems
• The operators min and max on the polynomial hierarchy

Cited in

(6)

• Functions computable in polynomial space
• scientific article; zbMATH DE number 4041256 (Why is no real title available?)
• Iterative Characterizations of Computable Unary Functions: A General Method
• scientific article; zbMATH DE number 1136092 (Why is no real title available?)
• Towards a Unified Complexity Theory of Total Functions
• Nondeterministic functions and the existence of optimal proof systems

This page was built for publication: UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS

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