Journal article 1252 views
Separation results for the size of constant-depth propositional proofs
,
Samuel R Buss
Annals of Pure and Applied Logic, Volume: 136, Issue: 1-2, Pages: 30 - 55
Swansea University Author:
Arnold Beckmann
Full text not available from this repository: check for access using links below.
DOI (Published version): 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 relations...
| Published in: | Annals of Pure and Applied Logic |
|---|---|
| ISSN: | 0168-0072 |
| Published: |
2005
|
| Online Access: |
Check full text
|
| URI: | https://cronfa.swan.ac.uk/Record/cronfa13720 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| 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. |
|---|---|
| College: |
Faculty of Science and Engineering |
| Issue: |
1-2 |
| Start Page: |
30 |
| End Page: |
55 |