Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Theodoros Papamakarios:

TR21-074 | 3rd June 2021
Theodoros Papamakarios, Alexander Razborov

Space characterizations of complexity measures and size-space trade-offs in propositional proof systems

We identify two new big clusters of proof complexity measures equivalent up to
polynomial and $\log n$ factors. The first cluster contains, among others,
the logarithm of tree-like resolution size, regularized (that is, multiplied
by the logarithm of proof length) clause and monomial space, and clause
space, both ordinary and ... more >>>

ISSN 1433-8092 | Imprint