Mining the surface: witnessing the low complexity theorems of arithmetic

DOI10.1007/978-3-031-15298-6_24OpenAlexW4297809195MaRDI QIDQ6160756

Amirhossein Akbar Tabatabai

Publication date: 2 June 2023

Published in: Logic, Language, Information, and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-15298-6_24

zbMATH Keywords

Peano arithmeticordinal analysisprovably total recursive functionstotal search problems

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites Work

• The provably total NP search problems of weak second order bounded arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Elementary descent recursion and proof theory
• Ordinal notations and well-orderings in bounded arithmetic
• Notation systems for infinitary derivations
• The provably total search problems of bounded arithmetic
• POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
• A Characterisation of Definable NP Search Problems in Peano Arithmetic
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• The NP Search Problems of Frege and Extended Frege Proofs
• NP search problems in low fragments of bounded arithmetic
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• On the interpretation of non-finitist proofs–Part II
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Mining the surface: witnessing the low complexity theorems of arithmetic