Proof Complexity and Feasible Interpolation
Amirhossein Akbar Tabatabai · 2025
Read Proof Complexity and Feasible Interpolation by Amirhossein Akbar Tabatabai (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-03002.txt.
Introduction
Amirhossein Akbar Tabatabai surveys proof complexity, the study of how long the shortest proof of a claim must be. His 2025 survey centers on feasible interpolation, a method that builds hard theorems whose proofs balloon far past the claim's own length. The tour spans classic and non-classic logics alike.
Readers need only base logic and two complexity classes to follow. New terms are built as they arise. Hard theorems from this method expose the true cost of proof search in each system. Such limits shape what automated provers can hope to do. The survey opens the field to newcomers while keeping the core trick in view.
Catalog record
| CREATOR | Amirhossein Akbar Tabatabai |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 154 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-03002