### arnold beckmann's pages

## Separation results for the size of constant-depth propositional proofs

**File:** PDF-File

**Author:** Arnold Beckmann and Sam Buss

**Title:** Separation results for the size of constant-depth propositional proofs

**Journal:** Annals of Pure and Applied Logic 2005, **136**: 30-55

Festschrift on the occasion of Wolfram Pohlers' 60th birthday

**DOI:** 10.1016/j.apal.2005.05.002

**Abstract:**
This paper proves exponential separations between
depth d-LK and depth (d+^{1}/_{2})-LK for every
d in 0, 1/2, 1, 1 1/2,... utilizing the order induction principle.
As a consequence, we obtain an exponential separation between
depth d-LK and depth (d+1)-LK for d in 0,1,2,... .
We investigate the relationship between the sequence-size, tree-size and
height of depth d-LK-derivations for d in 0, 1/2, 1, 1 1/2,...
and describe transformations between them.

We define a general method to lift
principles requiring exponential tree-size
(d+1/2)-LK-refutations for d in 0,1,2,...
to principles requiring exponential sequence-size d-LK-refutations,
which will be described for the Ramsey principle and d=0.
From this we also deduce width lower bounds for
resolution refutations of the Ramsey principle.