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

• scientific article; zbMATH DE number 4059391
• Characterising polynomial time computable functions using theories with weak set existence principles
• Theories with self-application and computational complexity.
• A second order version of S₂ⁱ and U₂¹
• scientific article; zbMATH DE number 4066875

zbMATH Keywords

interpretabilitycomplexity classesbounded arithmeticinductionprovably recursive functionspolynomial time hierarchybounded complexitysecond order theoriesweak comprehension

Mathematics Subject Classification ID

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 (7)

• 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?)
• Title not available (Why is that?)
• Theories with self-application and computational complexity.

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)