Function operators spanning the arithmetical and the polynomial hierarchy
From MaRDI portal
Publication:3060205
DOI10.1051/ita/2010020zbMath1213.68294MaRDI QIDQ3060205
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
Boolean hierarchy; polynomial hierarchy; arithmetical hierarchy; inversion of functions; minimalization; P versus NP; first value operator; NP versus coNP
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