Switch to: References

Add citations

You must login to add citations.
  1. Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem.Neil Thapen - 2011 - Archive for Mathematical Logic 50 (7):665-680.
    We give a new characterization of the strict $$\forall {\Sigma^b_j}$$ sentences provable using $${\Sigma^b_k}$$ induction, for 1 ≤ j ≤ k. As a small application we show that, in a certain sense, Buss’s witnessing theorem for strict $${\Sigma^b_k}$$ formulas already holds over the relatively weak theory PV. We exhibit a combinatorial principle with the property that a lower bound for it in constant-depth Frege would imply that the narrow CNFs with short depth j Frege refutations form a strict hierarchy with (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • 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 (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•