Delineating classes of computational complexity via second order theories with weak set existence principles. I
DOI10.2307/2275511zbMATH Open0819.03030OpenAlexW2155681304MaRDI QIDQ4836045FDOQ4836045
Authors: Aleksandar Ignjatović 
Publication date: 8 June 1995
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2275511
Recommendations
interpretabilitycomplexity classesbounded arithmeticinductionprovably recursive functionspolynomial time hierarchybounded complexitysecond order theoriesweak comprehension
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) First-order arithmetic and fragments (03F30) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)
Cited In (12)
- Techniques in weak analysis for conservation results
- Title not available (Why is that?)
- New Computational Paradigms
- Title not available (Why is that?)
- Arithmetic theories for computational complexity problems
- Title not available (Why is that?)
- On parallel hierarchies and R ki
- Title not available (Why is that?)
- Characterising polynomial time computable functions using theories with weak set existence principles
- Intrinsic theories and computational complexity
- Theories with self-application and computational complexity.
- Complexity hierarchies beyond elementary
This page was built for publication: Delineating classes of computational complexity via second order theories with weak set existence principles. I
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4836045)
