Proof Complexity of Linear Logics
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912861688692736 |
|---|---|
| author | Tabatabai, Amirhossein Akbar Jalali, Raheleh |
| author_facet | Tabatabai, Amirhossein Akbar Jalali, Raheleh |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22393 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Proof Complexity of Linear Logics Tabatabai, Amirhossein Akbar Jalali, Raheleh Logic in Computer Science Computational Complexity Logic 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. |
| title | Proof Complexity of Linear Logics |
| topic | Logic in Computer Science Computational Complexity Logic |
| url | https://arxiv.org/abs/2601.22393 |