Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Height-restrictions:
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