Function operators spanning the arithmetical and the polynomial hierarchy

DOI10.1051/ita/2010020zbMath1213.68294OpenAlexW2140119625MaRDI QIDQ3060205

Armin Hemmerling

Publication date: 1 December 2010

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/44607

zbMATH Keywords

Boolean hierarchypolynomial hierarchyarithmetical hierarchyinversion of functionsminimalizationP versus NPfirst value operatorNP versus coNP

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Hausdorff-Ershov hierarchy in Euclidean spaces
• The complexity of optimization problems
• On truth-table reducibility to SAT
• Classical recursion theory. The theory of functions and sets of natural numbers
• A taxonomy of complexity classes of functions
• Complexity theory and cryptology. An introduction to cryptocomplexity.
• On degrees of unsolvability
• Turing Computability
• Bounded Query Classes
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• A survey of one-way functions in complexity theory
• Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited
• Hierarchies of Primitive Recursive Functions
• Rekursionszahlen und die Grzegorczyk-Hierarchie
• Computability and Recursion
• General Recursive Functions

This page was built for publication: Function operators spanning the arithmetical and the polynomial hierarchy