Witnessing flows in arithmetic

DOI10.1017/s0960129524000185MaRDI QIDQ6646013

Amirhossein Akbar Tabatabai

Publication date: 29 November 2024

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

zbMATH Keywords

bounded arithmeticordinal analysistotal search problemslocal search programs

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• 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
• Unnamed Item
• The provably total NP search problems of weak second order bounded arithmetic
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
• Bounded arithmetic and the polynomial hierarchy
• Elementary descent recursion and proof theory
• Ordinal notations and well-orderings in bounded arithmetic
• Provability algebras and proof-theoretic ordinals. I
• Notation systems for infinitary derivations
• The provably total search problems of bounded arithmetic
• Quantified propositional calculi and fragments 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

This page was built for publication: Witnessing flows in arithmetic