Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > 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 >>>

TR21-158 | 12th November 2021
Noah Fleming, Toniann Pitassi, Robert Robere

Extremely Deep Proofs

Revisions: 1

We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, ... more >>>

ISSN 1433-8092 | Imprint