UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS

DOI10.1142/S0129054100000326zbMath0969.68084OpenAlexW2084342799MaRDI QIDQ4528761

Heinz Schmitz, Heribert Vollmer, Sven Kosub

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)

Related Items (2)

Nondeterministic functions and the existence of optimal proof systems ⋮ Functions computable in polynomial space

Cites Work

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

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