Truth definition for $\Delta _ 0$ formulas and PSPACE computations

DOI10.4064/fm578-1-2020zbMath1496.03240OpenAlexW3039392985MaRDI QIDQ5146427

Konrad Zdanowski

Publication date: 25 January 2021

Published in: Fundamenta Mathematicae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4064/fm578-1-2020

zbMATH Keywords

truth predicatebounded arithmeticfirst-order arithmeticsecond-order arithmeticPSPACE

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Second- and higher-order arithmetic and fragments (03F35) Complexity of proofs (03F20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The computational complexity of logical theories
• Truth definitions without exponentiation and the Σ₁ collection scheme
• Lower and upper bounds for the provability of Herbrand consistency in weak arithmetics
• A sharp version of the bounded Matijasevich conjecture and the end-extension problem
• On Wilkie and Paris’s notion of fullness
• Improved witnessing and local improvement principles for second-order bounded arithmetic

This page was built for publication: Truth definition for $\Delta _ 0$ formulas and PSPACE computations