Proof Complexity of Linear Logics
Proving proof-size lower bounds for $\mathbf{LK}$, the sequent calculus for classical propositional logic, remains one of the major open problems in proof complexity. We shed new light on this challenge by isolating the power of structural rules and showing that their combination is dramatically stronger than any individual structural rule alone, even in the presence of the controlled structural rules provided by linear exponentials. It is easy to see that $\mathbf{LK}$ without the weakening rule is significantly weaker than $\mathbf{LK}$ with respect to proof complexity. It therefore…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.22393
curl -X POST /api/v1/records/arxiv/2601.22393/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.22393/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'