Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with supercritical:
TR16-203 | 21st December 2016
Christoph Berkholz, Jakob Nordström

Supercritical Space-Width Trade-offs for Resolution

We show that there are CNF formulas which can be refuted in resolution
in both small space and small width, but for which any small-width
proof must have space exceeding by far the linear worst-case upper
bound. This significantly strengthens the space-width trade-offs in
[Ben-Sasson '09]}, and provides one more ... more >>>

ISSN 1433-8092 | Imprint