Function operators spanning the arithmetical and the polynomial hierarchy

DOI10.1051/ita/2010020zbMath1213.68294MaRDI 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 hierarchy; polynomial hierarchy; arithmetical hierarchy; inversion of functions; minimalization; P versus NP; first value operator; NP versus coNP

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

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

03D55: Hierarchies of computability and definability

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