Proof Complexity of Linear Logics

Amirhossein Akbar Tabatabai, Raheleh Jalali, Bernoulli Institute, University of Groningen, Department of Computer Science, University of Bath · 2026

Read Proof Complexity of Linear Logics by Amirhossein Akbar Tabatabai, Raheleh Jalali, Bernoulli Institute, University of Groningen, Department of Computer Science, University of Bath (2026) 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-2601-22393.txt.

Introduction

Amirhossein Akbar Tabatabai and Raheleh Jalali probe the proof strength of linear logics. Proof complexity asks how long a proof must be. Their 2026 preprint notes that lower bounds for the classic sequent calculus remain a major open problem. They shed new light by isolating the power of structural rules.

They show that the rules, combined, are vastly stronger than any one alone. They prove exponential gaps that make the point sharp. The work helps map what makes proofs blow up. That map guides logic, verification, and automated proof. It is a firm step on a hard road.

Catalog record

CREATORAmirhossein Akbar Tabatabai, Raheleh Jalali, Bernoulli Institute, University of Groningen, Department of Computer Science, University of Bath
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE127 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22393

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Proof Complexity of Linear Logics Amirhossein Akbar Tabatabai, Raheleh Jalali, Bernoulli Institute, University of Groningen, Department of Computer Science, University of Bath Abstract Proving proof-size lower bounds for 𝐋𝐊 \mathbf{LK} , the sequent calculus for classical propositional logic, remains a major open problem in proof complexity. We shed new light on this challenge by isolating the power of structural rules, showing that their combination is extremely stronger than any single rule alone. We establish exponential (resp. sub-exponential) proof-size lower bounds for 𝐋𝐊 \mathbf{LK} without contraction (resp. weakening) for formulas with short 𝐋𝐊 \mathbf{LK} -proofs. Concretely, we work with the Full Lambek calculus with exchange, 𝐅𝐋 𝐞 \mathbf{FL_{e}} , and its contraction-extended variant, 𝐅𝐋 𝐞𝐜 \mathbf{FL_{ec}} , substructural systems underlying linear logic. We construct families of 𝐅𝐋 𝐞 \mathbf{FL_{e}} -provable (resp. 𝐅𝐋 𝐞𝐜 \mathbf{FL_{ec}} -provable) formulas that require exponential-size (resp. sub-exponential-size) proofs in affine linear logic 𝐀𝐋𝐋 \mathbf{ALL} (resp. relevant linear logic 𝐑𝐋𝐋 \mathbf{RLL} ), but admit polynomial-size proofs once contraction (resp. weakening) is restored. This yields exponential lower bounds on proof-size of 𝐅𝐋 𝐞 \mathbf{FL_{e}} -provable formulas in 𝐀𝐋𝐋 \mathbf{ALL} and hence for 𝐌𝐀𝐋𝐋 \mathbf{MALL} , 𝐀𝐌𝐀𝐋𝐋 \mathbf{AMALL} , and full classical linear logic 𝐂𝐋𝐋 \mathbf{CLL} . Finally, we exhibit formulas with polynomial-size 𝐅𝐋 𝐞 \mathbf{FL_{e}} -proofs that nevertheless require exponential-size proofs in cut-free 𝐋𝐊 \mathbf{LK} , establishing exponential speed-ups between various linear calculi and their cut-free counterparts. Keywords. Proof complexity, linear logics, substructural logics, exponential lower bound, (monotone) feasible interpolation, vector addition systems, Chu’s construction. 1 Introduction Proof complexity is an interdisciplinary field that uses tools from logic, complexity theory, and combinatorics. The main goal of proof complexity is to understand the complexity of theorem-proving procedures. In other words, it aims to determine how efficient proof systems are when they prove their theorems. This naturally leads to the central problem of finding lower bounds on proof size in proof systems. The difficulty of this problem is what makes it interesting: its deep connection with computational complexity. The field was motivated by the seminal work of Cook and Reckhow [ 16 ] , who established a fundamental connection between proof size and the separation of complexity classes. They showed that NP \neq coNP iff there are superpolynomial lower bounds for every proof system for classical propositional logic, \mathsf{CPC} . This conjectured lower bound for arbitrary proof systems has never been established. In fact, despite decades of research, even the single case of the Frege system (the standard proof system for \mathsf{CPC} , polynomially equivalent to sequent calculus \mathbf{LK} and natural deduction) still resists all known lower-bound techniques. Facing such a strict barrier, progress has therefore focused on weaker systems. The first natural approach was restricting the form of formulas and deduction rules (sometimes in algebraic and semi-algebraic disguise). This led to a plethora of exponential lower bound results for Resolution [ 20 ] , the Nullstellensatz system [ 7 ] , Cutting Planes [ 10 , 40 ] , Polynomial Calculus [ 15 , 44 ] , and bounded-depth Frege systems [ 1 , 8 , 39 , 34 ] . Another successful way of avoiding the \mathbf{LK} barrier is to change classical logic itself, either by weakening it (e.g., forbidding full involution \neg\neg A\to A ) or by extending the language (e.g., with modalities). As these logics are usually \mathrm{PSPACE} -hard, their study is closely connected to another notoriously hard problem in complexity theory, namely \mathrm{NP} vs. \mathrm{PSPACE} . Since this problem is, in a sense, easier than \mathrm{NP} vs. \mathrm{coNP} , one may expect stronger results on this front. Indeed, there are many known exponential lower bounds for these systems, including Frege systems for intuitionistic and some modal logics [ 22 , 23 , 24 ] , superintuitionistic and modal logics of infinite branching [ 28 , 29 ] , intuitionistic substructural logics [ 26 ] , and propositional default logic [ 9 ] . Owing to their expressive power and numerous applications in computer science, the proof complexity of these non-classical systems has received extensive attention in recent years. 1.1 Our Contribution In this work, we follow the same strategy of weakening classical logic; however, our approach differs conceptually. To illustrate the role of full involution, the backbone of classical reasoning , we keep the axiom (\neg\neg A\to A) intact and also allow unrestricted formulas in our proofs. Instead, we weaken the logic by pruning its structural rules . By removing contraction, weakening, and the cut rule one at a time, (sometimes even with controlled structural rules provided by linear exponentials), we obtain three main results that isolate the precise contribution of each rule to the strength of classical proof systems. Our main results are summarized in Table 1 . To state our results concisely, we introduce the following notion. Let G , H , and P be sequent calculi (possibly for different logics). We write G\leq_{P}H if, for every sequent S provable in P , \text{if}\qquad G\vdash^{\pi}S\qquad\text{then}\qquad\exists|\pi^{\prime}|\leq|\pi|^{O(1)}\;\text{s.t.}\;H\vdash^{\pi^{\prime}}S, where by G\vdash^{\pi}S we mean S has a G -proof \pi . Similarly for H\vdash^{\pi^{\prime}}S . Recall that \mathbf{CFL_{e}},\mathbf{CFL_{ew}},\mathbf{CFL_{ec}} denote the classical full Lambek calculus with exchange, with exchange and weakening, and with exchange and contraction, respectively; \mathbf{MALL},\mathbf{AMALL},\mathbf{RMALL} denote the multiplicative–additive fragment of linear logic, with weakening, and with contraction, respectively; and \mathbf{CLL},\mathbf{ALL},\mathbf{RLL} denote full classical linear logic, with weakening, and with contraction, respectively; \mathbf{FL_{e}} , \mathbf{IMALL} , and \mathbf{ILL} are the intuitionistic counterparts of \mathbf{CFL_{e}} , \mathbf{MALL} and \mathbf{CLL} , respectively. 1.1.1 Contraction-free Calculi We prove an exponential separation between \mathbf{ALL} and \mathbf{LK} for \mathbf{FL_{e}} -provable formulas. More precisely, we identify a sequence \{A_{n}\}_{n\in\mathbb{N}} of \mathbf{FL_{e}} -provable formulas such that every \mathbf{ALL} -proof of A_{n} has size 1 1 1 The size of a formula or a proof is the number of symbols it contains. exponential in |A_{n}| , whereas A_{n} has polynomial-size proofs in \mathbf{LK} . Therefore, \mathbf{LK}\nleq_{\mathbf{FL_{e}}}\mathbf{ALL} . This implies an exponential lower bound on the proof size of \mathbf{FL_{e}} -provable formulas in \mathbf{ALL} and hence for each of the following contraction-free calculi G\in\{\mathbf{CFL_{e}},\mathbf{CFL_{ew}},\mathbf{MALL},\mathbf{AMALL},\mathbf{CLL}\}. Note that the separating formulas A_{n} are ! -free, since they are written in the language of \mathbf{FL_{e}} . Without this ! -freeness, separation results are trivial. The reason is the high decision complexity of \mathbf{ALL} . In fact, \mathbf{ALL} is \mathrm{TOWER} -complete, where \mathrm{TOWER} denotes the class of problems decidable in time bounded by a tower of exponentials [ 35 ] . By a simple argument, proof size of \mathbf{ALL} -provable formulas cannot be bounded by any fixed-height tower: otherwise, one could enumerate all proofs and decide provability within that bound, contradicting \mathrm{TOWER} -hardness. In contrast, every formula has an exponential-size proof in \mathbf{LK} , establishing the separation. For \mathbf{CLL} , the situation is even more extreme, as its decision problem is \Sigma^{0}_{1} -complete and therefore undecidable [ 36 ] . For ! -free formulas, however, \mathbf{ALL} is conservative over \mathbf{MALL} , so its decision problem remains \mathrm{PSPACE} -complete [ 21 ] , making the exponential separation interesting. Moreover, while one might hope that employing exponentials in proofs could simplify hard ! -free formulas, our results show that even the full machinery of exponential linearity does not reduce the complexity of these formulas. 1.1.2 Weakening-free Calculi Similar to the situation for

Read the complete text