Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUPERCRITICAL TRADEOFF:
Reports tagged with supercritical tradeoff:
TR16-184 | 16th November 2016
Alexander Razborov

On Space and Depth in Resolution

We show that the total space in resolution, as well as in any other reasonable
proof system, is equal (up to a polynomial and $(\log n)^{O(1)}$ factors) to
the minimum refutation depth. In particular, all these variants of total space
are equivalent in this sense. The same conclusion holds for ... more >>>




ISSN 1433-8092 | Imprint