Characterising polynomial time computable functions using theories with weak set existence principles
From MaRDI portal
Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Recommendations
- Delineating classes of computational complexity via second order theories with weak set existence principles. I
- scientific article; zbMATH DE number 440477
- A weak constructive second-order arithmetic with extraction of algorithms computable in polynomial time
- A feasible theory for analysis
- A foundational delineation of poly-time
Cited in
(13)- A foundational delineation of poly-time
- A term rewriting characterization of the functions computable in polynomial space
- A second-order system for polytime reasoning based on Grädel's theorem.
- Applicative theories for the polynomial hierarchy of time and its levels
- scientific article; zbMATH DE number 4139739 (Why is no real title available?)
- Elementary explicit types and polynomial time operations
- scientific article; zbMATH DE number 4006252 (Why is no real title available?)
- scientific article; zbMATH DE number 4128804 (Why is no real title available?)
- A feasible theory for analysis
- Delineating classes of computational complexity via second order theories with weak set existence principles. I
- Function spaces for second-order polynomial time
- scientific article; zbMATH DE number 2201364 (Why is no real title available?)
- A weak constructive second-order arithmetic with extraction of algorithms computable in polynomial time
This page was built for publication: Characterising polynomial time computable functions using theories with weak set existence principles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2843916)
