Switch to: References

Add citations

You must login to add citations.
  1. Short refutations for an equivalence‐chain principle for constant‐depth formulas.Sam Buss & Ramyaa Ramyaa - 2018 - Mathematical Logic Quarterly 64 (6):505-513.
    We consider tautologies expressing equivalence‐chain properties in the spirit of Thapen and Krajíček, which are candidates for exponentially separating depth k and depth Frege proof systems. We formulate a special case where the initial member of the equivalence chain is fully specified and the equivalence‐chain implications are actually equivalences. This special case is shown to lead to polynomial size resolution refutations. Thus it cannot be used for separating depth k and depth propositional systems. We state some Håstad switching lemma conditions (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Towards NP – P via proof complexity and search.Samuel R. Buss - 2012 - Annals of Pure and Applied Logic 163 (7):906-917.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • An unexpected separation result in Linearly Bounded Arithmetic.Arnold Beckmann & Jan Johannsen - 2005 - Mathematical Logic Quarterly 51 (2):191-200.
    The theories Si1 and Ti1 are the analogues of Buss' relativized bounded arithmetic theories in the language where every term is bounded by a polynomial, and thus all definable functions grow linearly in length. For every i, a Σbi+1-formula TOPi, which expresses a form of the total ordering principle, is exhibited that is provable in Si+11 , but unprovable in Ti1. This is in contrast with the classical situation, where Si+12 is conservative over Ti2 w. r. t. Σbi+1-sentences. The independence (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
    Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond NP ≠ coNP. These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be (...)
    Download  
     
    Export citation  
     
    Bookmark   6 citations