Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CDCL:
Reports tagged with cdcl:
TR24-001 | 2nd January 2024
Sam Buss, Neil Thapen

A Simple Supercritical Tradeoff between Size and Height in Resolution

We describe CNFs in n variables which, over a range of parameters, have small resolution refutations but are such that any small refutation must have height larger than n (even exponential in n), where the height of a refutation is the length of the longest path in it. This is ... more >>>




ISSN 1433-8092 | Imprint