From determinism, non-determinism and alternation to recursion schemes for P, NP and Pspace (Invited Talk)

DOI10.4230/LIPICS.CSL.2013.24MaRDI QIDQ2958508zbMATH OpenOpenAlexFDO

Authors Isabel Oitavem

Publication date 2 February 2017

Full work available at URL https://doi.org/10.4230/lipics.csl.2013.24

zbMATH Keywords

computational complexityNPPrecursion schemesPspace

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7650818
• A recursion-theoretic approach to NP
• On the possibilities and limitations of pseudodeterministic algorithms
• P versus NP and computability theoretic constructions in complexity theory over algebraic structures
• scientific article; zbMATH DE number 2163035
• scientific article; zbMATH DE number 3954251
• Complexity of propositional proofs (invited talk)

This page was built for publication: From determinism, non-determinism and alternation to recursion schemes for P, NP and Pspace (Invited Talk)

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