No Cover Image

Journal article 537 views

Separation results for the size of constant-depth propositional proofs / Arnold Beckmann; 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.

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...

Full description

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: College of Science
Issue: 1-2
Start Page: 30
End Page: 55