Switch to: Citations

Add references

You must login to add references.
  1. Separation results for the size of constant-depth propositional proofs.Arnold Beckmann & Samuel R. Buss - 2005 - Annals of Pure and Applied Logic 136 (1-2):30-55.
    This paper proves exponential separations between depth d-LK and depth -LK for every utilizing the order induction principle. As a consequence, we obtain an exponential separation between depth d-LK and depth -LK for . We investigate the relationship between the sequence-size, tree-size and height of depth d-LK-derivations for , and describe transformations between them. We define a general method to lift principles requiring exponential tree-size -LK-refutations for to principles requiring exponential sequence-size d-LK-refutations, which will be described for the Ramsey principle (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • An exponential separation between the parity principle and the pigeonhole principle.Paul Beame & Toniann Pitassi - 1996 - Annals of Pure and Applied Logic 80 (3):195-228.
    The combinatorial parity principle states that there is no perfect matching on an odd number of vertices. This principle generalizes the pigeonhole principle, which states that for a fixed bipartition of the vertices, there is no perfect matching between them. Therefore, it follows from recent lower bounds for the pigeonhole principle that the parity principle requires exponential-size bounded-depth Frege proofs. Ajtai previously showed that the parity principle does not have polynomial-size bounded-depth Frege proofs even with the pigeonhole principle as an (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations