🔢 mathematics

Proof Complexity of Linear Logics

This paper establishes exponential proof-size lower bounds for various linear logics by demonstrating that the combination of structural rules (contraction and weakening) and the cut rule provides dramatic speed-ups over systems lacking these specific components, thereby isolating their individual and collective power in proof complexity.

Original authors: Amirhossein Akbar Tabatabai, Raheleh Jalali

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Amirhossein Akbar Tabatabai, Raheleh Jalali

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, impossible-looking puzzle. In the world of logic, this puzzle is proving that a specific statement is true. For decades, the biggest mystery in this field has been: "How hard is it to prove things in the standard system of logic (called LK)?" We know that if you take away certain "helper tools" (rules) from the system, the puzzle gets harder. But exactly how much harder? And which tool is the real MVP?

Two researchers, Amirhossein Akbar Tabatabai and Raheleh Jalali, decided to play a game of "remove the tools" to see what happens. They didn't just guess; they built mathematical proofs to show exactly how the difficulty explodes when you take away specific rules.

The Three Magic Tools

Think of a logic proof like building a house. You have three special tools that make construction fast and easy:

Contraction: This is like a photocopier. If you need two bricks of the same type, you can just photocopy one instead of finding two separate ones. It lets you reuse information freely.
Weakening: This is like a "free pass" card. It lets you add extra, useless bricks to your pile just because you feel like it, without breaking anything.
Cut: This is the ultimate shortcut. It's like saying, "I know this intermediate step is true, so let's just skip the proof of that step and move on." It connects two parts of the puzzle instantly.

The Big Discovery: The Photocopier is a Monster

The authors wanted to know: What happens if you take away the Photocopier (Contraction)?

They found a specific family of puzzles (called "Clique-Color formulas," which are essentially complex graph problems about connecting dots and coloring them) that are easy to solve if you have the Photocopier. In the standard system, you can solve them with a proof that is reasonably sized (polynomial size).

But, if you ban the Photocopier (working in a system called LLW), the size of the proof needed to solve these exact same puzzles explodes. It doesn't just get a little bigger; it grows exponentially. To put it in perspective: if the easy proof is the size of a postcard, the hard proof without the Photocopier would be the size of the entire internet.

Crucially, the paper argues against a common hope: Some people thought that maybe we could use a "controlled" version of the Photocopier (using special "exponential" rules in linear logic) to fix this. The authors proved this is false. Even with these fancy, controlled tools, the proof still blows up to an exponential size. The absence of the full, unrestricted Photocopier is a fundamental barrier that cannot be bypassed.

The Second Discovery: The Shortcut is a Superpower

Next, they looked at the Shortcut (Cut).

They took a system that already has the Photocopier and the Free Pass (Weakening) and asked: "What if we remove the Shortcut?"

The result was shocking. They found puzzles that are easy to prove in a very weak system (called FLe, which has neither the Photocopier nor the Free Pass, but does have the Shortcut) but become exponentially harder if you remove the Shortcut, even if you keep the Photocopier and Free Pass.

This proves that the Cut rule is incredibly powerful. It provides an exponential speed-up. It's not just a minor convenience; it's the difference between solving a puzzle in a lifetime versus solving it in the heat death of the universe.

What They Ruled Out

The paper explicitly rules out the idea that "controlled" versions of these rules (like the linear exponentials in linear logic) can save the day.

Against the "Controlled" Photocopier: They showed that even with the full machinery of linear exponentials, you cannot get a short proof for these specific problems if you lack the full Contraction rule.
Against the "Controlled" Shortcut: They showed that even if you have Contraction and Weakening, removing the Cut rule still causes an exponential explosion in proof size.

How Sure Are They?

The authors are 100% sure about these specific results. They didn't just simulate this on a computer or suggest it might be true. They constructed rigorous mathematical proofs (using a clever technique called "Chu's translation" to move problems between different logical worlds) that demonstrate these exponential lower bounds.

They proved that:

There is a sequence of formulas that requires exponential-size proofs in systems without Contraction (like LLW), even though they have polynomial-size proofs in standard logic.
There is a sequence of formulas that requires exponential-size proofs in systems without Cut (like LK without Cut), even though they have polynomial-size proofs in weaker systems that do have Cut.

The Bottom Line

This paper is like finding out that the "Photocopier" and the "Shortcut" are not just helpful tools; they are the engines that make modern logic run fast. Without them, the complexity of proving things doesn't just increase a little; it goes off the charts. The authors have successfully isolated these rules and shown that their combination is dramatically stronger than any single rule alone, even when you try to cheat with controlled versions of those rules.

They haven't solved the biggest open problem in the field (which is proving lower bounds for the standard system with all rules), but they have cracked open the door to understand why those rules are so powerful, revealing that the absence of just one of them turns a manageable puzzle into an impossible nightmare.

Technical Summary: Proof Complexity of Linear Logics

1. Problem Statement

The central challenge in proof complexity is establishing superpolynomial lower bounds on proof size for classical propositional logic (CPC), specifically within the Frege system or the sequent calculus LK. Despite decades of research, this remains an open problem, closely linked to the separation of complexity classes (NP vs. coNP).

To circumvent the barriers of classical logic, researchers have traditionally focused on:

Restricting the form of formulas or deduction rules (e.g., Resolution, Cutting Planes).
Weakening the logic itself (e.g., intuitionistic or modal logics) or extending the language.

This paper addresses the problem by systematically isolating the power of structural rules (contraction, weakening, and cut) within the framework of linear and substructural logics. The authors investigate how the removal of these rules individually or in combination affects proof complexity, particularly in the presence of linear exponentials (the "!" modality), which provide controlled structural reasoning.

2. Methodology

The authors employ two primary interdisciplinary methods to establish their results:

2.1. Chu's Translation

The paper adapts Chu's construction, a categorical technique typically used to generate self-dual categories from symmetric monoidal closed categories. In this context, it is utilized as a proof-theoretic translation:

Mechanism: The authors define translation functions $(\cdot)^t$ and $(\cdot)^s$ that map classical linear formulas to intuitionistic linear formulas.
Function: This translation allows proofs in classical contraction-free systems (like LLW) to be feasibly transformed into proofs in their intuitionistic counterparts (like ILLW) without distorting the disjunction connectives where computational content is concentrated.
Application: By combining this translation with circuit-extraction techniques suited for intuitionistic settings, the authors transfer circuit lower bounds into proof-size lower bounds for classical systems. This isolates the contraction rule as a potential barrier for lower bounds in LK.

2.2. Feasible Interpolation and Cut-Freeness

The second method leverages monotone feasible interpolation, a tool introduced by Krajíček for proving lower bounds in classical proof systems.

Mechanism: The authors construct a specific extension of the substructural calculus FLe (denoted as $G$ ) that includes initial sequents mimicking classical reasoning (specifically weakening and contraction) on negation-normal-form formulas.
Application: They demonstrate that short proofs in this extended system can be transformed into short FLe-proofs. Conversely, they show that if a cut-free system (like $LK^-$ ) could prove these sequents efficiently, it would imply the existence of small monotone circuits for the Clique-Color formula.
Connection: Since the Clique-Color formula requires exponentially large monotone circuits (a known result in circuit complexity), the existence of short cut-free proofs is ruled out, establishing an exponential separation.

3. Key Contributions and Results

3.1. Contraction-Free Calculi (The Power of Contraction)

The authors prove an exponential separation between LLW (Affine Linear Logic, which lacks contraction but has weakening) and LK (Classical Logic).

Result: They identify a sequence of formulas $\{A_n\}$ provable in FLe (and thus in LK) that admit polynomial-size proofs in LK but require exponential-size proofs in LLW.
Significance: This result holds even for formulas that do not use the exponential modality "!". It demonstrates that the full machinery of linear exponentials cannot compensate for the absence of the contraction rule. Consequently, exponential lower bounds are established for FLe-provable formulas in LLW, MALL, MALLw, and full classical linear logic LL.
Implication: The contraction rule is shown to be a critical component for proof compression, and its absence leads to an exponential blow-up that cannot be mitigated by other structural rules.

3.2. Weakening-Free Calculi

The paper briefly addresses the role of weakening.

Observation: Separating contraction-free systems with weakening (like CFLec) from LK is considered trivial due to the high decision complexity (Ackermann-completeness) of these systems. The decision problem for such systems is already so hard that proof-size lower bounds are immediate consequences of complexity class separations, rendering a detailed proof-complexity analysis less novel in this specific context.

3.3. Cut-Free Calculi (The Power of Cut)

The authors investigate the impact of the cut rule by comparing systems with and without it.

Result: They construct a sequence of sequents $\{S_n\}$ that have polynomial-size proofs in the weak system FLe (which lacks both contraction and weakening) but require exponential-size proofs in $LK^-$ (Classical Logic without cut).
Significance: This demonstrates that the cut rule alone provides an exponential speed-up over the combination of weakening and contraction. Even when contraction and weakening are fully available, removing the cut rule leads to an exponential increase in proof size.
Scope: This establishes exponential separations between various linear calculi (FLe, MALL, LL, etc.) and their cut-free counterparts.

4. Summary of Separations

The paper provides a comprehensive table of results (Table 1 in the text) summarizing the simulation relationships between various calculi. Key takeaways include:

LLW vs. LK: Exponential separation exists for FLe-provable formulas.
Cut-free vs. Full Systems: Exponential separations exist between any of the listed calculi and their cut-free versions.
Role of Exponentials: The hardness results are intrinsic to the absence of structural rules; the addition of controlled structural rules via the "!" modality does not reduce the hardness.

5. Significance and Claims

The authors claim that their work sheds new light on the challenge of proving lower bounds for LK by isolating the specific contributions of structural rules.

Conceptual Contribution: The adaptation of Chu's construction into a proof-theoretic translation is presented as a significant conceptual contribution, offering a new approach to the proof complexity of LK via its substructural fragments.
Resolution of Open Questions: The results positively answer a question posed in prior work [26] regarding the extension of exponential lower bounds to sequent calculi with cut.
Intrinsic Hardness: The paper argues that the exponential blow-up observed is intrinsic to the absence of specific structural rules (contraction or cut) and cannot be compensated for by other mechanisms, even in the presence of linear exponentials.

The authors remain modest regarding future implications, noting that comparisons among cut-free systems and separations between logics with only weakening versus only contraction remain open problems. They also suggest future work on extending these results to Extended Frege (EF) systems.