Bounded theories for polyspace computability
Complexity of computation (including implicit computational complexity) (03D15) Proof theory in general (including proof-theoretic semantics) (03F03) Cut-elimination and normal-form theorems (03F05) First-order arithmetic and fragments (03F30) Second- and higher-order arithmetic and fragments (03F35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Summary: We present theories of bounded arithmetic and weak analysis whose provably total functions (with appropriate graphs) are the polyspace computable functions. More precisely, inspired in Ferreira's systems \(\mathrm{PTCA}\), \(\Sigma^b_1\text{-}\mathrm{NIA}\) and \(\mathrm{BTFA}\) in the polytime framework, we propose analogue theories concerning polyspace computability. Since the techniques we employ in the characterization of \(\mathrm{PSPACE}\) via formal systems (e.g. Herbrand's theorem, cut elimination theorem and the expansion of models) are similar to the ones involved in the polytime setting, we focus on what is specific of polyspace and explains the lift from \(\mathrm{PTIME}\) to \(\mathrm{PSPACE}\).
- scientific article; zbMATH DE number 4128804
- scientific article; zbMATH DE number 4104951
- scientific article; zbMATH DE number 4132145
- scientific article; zbMATH DE number 819737
- scientific article; zbMATH DE number 408792
- Computability on quasi-Polish spaces
- Bounded linear logic: A modular approach to polynomial-time computability
- scientific article; zbMATH DE number 4066875
- Computable fields and the bounded Turing reduction
- Polynomially bounded recursive realizability
- A Conservation Result Concerning Bounded Theories and the Collection Axiom
- A feasible theory for analysis
- An interpretation of \(S_2^1\) in \(\Sigma_1^b\)-NIA
- Bounded arithmetic and the polynomial hierarchy
- Computer Science Logic
- Counting as integration in feasible analysis
- Fragments of Bounded Arithmetic and Bounded Query Classes
- Groundwork for weak analysis
- scientific article; zbMATH DE number 4160708 (Why is no real title available?)
- scientific article; zbMATH DE number 806747 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 850763 (Why is no real title available?)
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Interpretability in Robinson's Q
- The provably total NP search problems of weak second order bounded arithmetic
- The Riemann integral in weak systems of analysis
This page was built for publication: Bounded theories for polyspace computability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2450770)
