Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Arnold Beckmann:

TR13-092 | 19th June 2013
Pavel Pudlak, Arnold Beckmann, Neil Thapen

Parity Games and Propositional Proofs

Revisions: 1

A propositional proof system is \emph{weakly automatizable} if there
is a polynomial time algorithm which separates satisfiable formulas
from formulas which have a short refutation in the system, with
respect to a given length bound. We show that if the resolution
proof system is weakly automatizable, ... more >>>

TR03-034 | 17th March 2003
Arnold Beckmann

Height restricted constant depth LK

Height restricted constant depth LK is a natural restriction of
Gentzen's propositional proof system LK. A sequence of LK-formulas
has polylogarithmic-height restricted depth-d-LK proofs iff the
n-th formula in the sequence possesses LK-proofs where cut-formulas
are of depth d+1 with small bottom fanin
and of ... more >>>

ISSN 1433-8092 | Imprint