Switch to: References

Add citations

You must login to add citations.
  1. Conservative fragments of $${{S}^{1}{2}}$$ and $${{R}^{1}{2}}$$. [REVIEW]Chris Pollett - 2011 - Archive for Mathematical Logic 50 (3):367-393.
    Conservative subtheories of $${{R}^{1}_{2}}$$ and $${{S}^{1}_{2}}$$ are presented. For $${{S}^{1}_{2}}$$, a slight tightening of Jeřábek’s result (Math Logic Q 52(6):613–624, 2006) that $${T^{0}_{2} \preceq_{\forall \Sigma^{b}_{1}}S^{1}_{2}}$$ is presented: It is shown that $${T^{0}_{2}}$$ can be axiomatised as BASIC together with induction on sharply bounded formulas of one alternation. Within this $${\forall\Sigma^{b}_{1}}$$ -theory, we define a $${\forall\Sigma^{b}_{0}}$$ -theory, $${T^{-1}_{2}}$$, for the $${\forall\Sigma^{b}_{0}}$$ -consequences of $${S^{1}_{2}}$$. We show $${T^{-1}_{2}}$$ is weak by showing it cannot $${\Sigma^{b}_{0}}$$ -define division by 3. We then consider what (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic.Arnold Beckmann & Samuel R. Buss - 2009 - Journal of Mathematical Logic 9 (1):103-138.
    The complexity class of [Formula: see text]-polynomial local search problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 ≤ i ≤ k + 1, the [Formula: see text]-definable functions of [Formula: see text] are characterized in terms of [Formula: see text]-PLS problems. These [Formula: see text]-PLS problems can be defined in a weak base theory such as [Formula: see text], and proved to be total in [Formula: see text]. Furthermore, the [Formula: (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • 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  
  • 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  
  • 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