Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CUT-FREE LK:
Reports tagged with cut-free LK:
TR21-176 | 30th November 2021
Theodoros Papamakarios

A super-polynomial separation between resolution and cut-free sequent calculus

We show a quadratic separation between resolution and cut-free sequent calculus width. We use this gap to get, for the first time, first, a super-polynomial separation between resolution and cut-free sequent calculus for refuting CNF formulas, and secondly, a quadratic separation between resolution width and monomial space in polynomial calculus ... more >>>




ISSN 1433-8092 | Imprint