Bounded theories for polyspace computability

DOI10.4171/PM/1936MaRDI QIDQ2450770zbMATH OpenFDO

Authors Ricardo Bianconi, Gilda Ferreira, Emmanuel Sirimal Silva

Publication date 16 May 2014

Published in Portugaliae Mathematica. Nova Série (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4171/PM/1936

zbMATH Keywords

bounded arithmeticconservation resultscut eliminationpolyspace computabilityweak analysis

Mathematics Subject Classification ID

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)

Recommendations

• 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

Cites work

• 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

Cited in

(3)

• Truth definition for _0 formulas and PSPACE computations
• Computer Science Logic
• The computational power of bounded arithmetic from the predicative viewpoint

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)