A recursion-theoretic approach to NP

DOI10.1016/j.apal.2011.01.010zbMath1233.03046OpenAlexW2016014073MaRDI QIDQ639668

Isabel Oitavem

Publication date: 22 September 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.01.010

zbMATH Keywords

computational complexityNPBellantoni-Cook characterization of FPTimeimplicit characterizationpurely recursion-theoretic characterization of NPrecursion scheme

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Inductive definability (03D70)

Related Items

Algorithmically broad languages for polynomial time and space, The Power of Non-determinism in Higher-Order Implicit Complexity, Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting), The polynomial hierarchy of functions and its levels, Implicit recursion-theoretic characterizations of counting classes, Implicit computation complexity in higher-order programming languages

Cites Work

• Unnamed Item
• A new recursion-theoretic characterization of the polytime functions
• Separating NC along the \(\delta\) axis
• Characterizing PSPACE with pointers
• Towards an Implicit Characterization of NC k
• Characterizing NC with tier 0 pointers