Recursion-theoretic alternation

DOI10.1007/978-3-031-64309-5_20MaRDI QIDQ7030901zbMATH OpenFDO

Authors Eduardo Skapinakis

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-64309-5_20

zbMATH Keywords

alternationimplicit complexitylogarithmic resourcestree recursion

Mathematics Subject Classification ID

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

Cites work

• A characterization of NC by tree recurrence
• A machine description and the hierarchy of initial Grzegorczyk classes
• A recursion-theoretic approach to NP
• Alternation
• Characterizing PSPACE with pointers
• Descriptive complexity of deterministic polylogarithmic time and space
• Gap-languages and log-time complexity classes
• scientific article; zbMATH DE number 176199 (Why is no real title available?)
• scientific article; zbMATH DE number 1390027 (Why is no real title available?)
• Nondeterministic stack register machines
• On uniformity within \(NC^ 1\)
• Proper hierarchies in polylogarithmic time and absence of complete problems
• Rudimentary Predicates and Relative Computation
• Separating NC along the \(\delta\) axis
• The graph of multiplication is equivalent to counting
• The polynomial hierarchy of functions and its levels
• The realm of primitive recursion
• Theory of Formal Systems. (AM-47)

This page was built for publication: Recursion-theoretic alternation

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