Switch to: References

Add citations

You must login to add citations.
  1. The provably total NP search problems of weak second order bounded arithmetic.Leszek Aleksander Kołodziejczyk, Phuong Nguyen & Neil Thapen - 2011 - Annals of Pure and Applied Logic 162 (6):419-446.
    We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout our search (...)
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • 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 (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Alternating minima and maxima, Nash equilibria and Bounded Arithmetic.Pavel Pudlák & Neil Thapen - 2012 - Annals of Pure and Applied Logic 163 (5):604-614.
    Download  
     
    Export citation  
     
    Bookmark   3 citations