14 found
Order:
  1.  23
    NP Search Problems in Low Fragments of Bounded Arithmetic.Jan Krajíček, Alan Skelley & Neil Thapen - 2007 - Journal of Symbolic Logic 72 (2):649 - 672.
    We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories $T_{2}^{2}$ and $T_{3}^{2}$.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  2. 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.
  3.  19
    Fragments of Approximate Counting.Samuel R. Buss, Leszek Aleksander Kołodziejczyk & Neil Thapen - 2014 - Journal of Symbolic Logic 79 (2):496-525.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  4.  19
    The Polynomial and Linear Hierarchies in Models Where the Weak Pigeonhole Principle Fails.Leszek Aleksander Kołodziejczyk & Neil Thapen - 2008 - Journal of Symbolic Logic 73 (2):578-592.
    We show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of S21 exists in which NP is not in the second level of the linear hierarchy; and that a model of S21 exists in which the polynomial hierarchy collapses to the linear hierarchy. Our methods are model-theoretic. We use the assumption about factoring to get a model in which the weak (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  5.  10
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  6.  9
    A Model-Theoretic Characterization of the Weak Pigeonhole Principle.Neil Thapen - 2002 - Annals of Pure and Applied Logic 118 (1-2):175-195.
    We bring together some facts about the weak pigeonhole principle from bounded arithmetic, complexity theory, cryptography and abstract model theory. We characterize the models of arithmetic in which WPHP fails as those which are determined by an initial segment and prove a conditional separation result in bounded arithmetic, that PV + lies strictly between PV and S21 in strength, assuming that the cryptosystem RSA is secure.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  7.  9
    Structures Interpretable in Models of Bounded Arithmetic.Neil Thapen - 2005 - Annals of Pure and Applied Logic 136 (3):247-266.
    We look for a converse to a result from [N. Thapen, A model-theoretic characterization of the weak pigeonhole principle, Annals of Pure and Applied Logic 118 175–195] that if the weak pigeonhole principle fails in a model K of bounded arithmetic, then there is an end-extension of K interpretable inside K. We show that if a model J of an induction-free theory of arithmetic is interpretable inside K, then either J is isomorphic to an initial segment of K , or (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  8.  12
    How Much Randomness is Needed for Statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2012 - In S. Barry Cooper (ed.), Annals of Pure and Applied Logic. pp. 395--404.
    In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle . The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ . While the Hippocratic approach is in general much more restrictive, there are cases where the (...)
    Direct download (12 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  29
    Weak Theories of Linear Algebra.Neil Thapen & Michael Soltys - 2004 - Archive for Mathematical Logic 44 (2):195-208.
    We investigate the theories of linear algebra, which were originally defined to study the question of whether commutativity of matrix inverses has polysize Frege proofs. We give sentences separating quantified versions of these theories, and define a fragment in which we can interpret a weak theory V 1 of bounded arithmetic and carry out polynomial time reasoning about matrices - for example, we can formalize the Gaussian elimination algorithm. We show that, even if we restrict our language, proves the commutativity (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  46
    Higher Complexity Search Problems for Bounded Arithmetic and a Formalized No-Gap Theorem.Neil Thapen - 2011 - Archive for Mathematical Logic 50 (7-8):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  
  11.  12
    How Much Randomness is Needed for Statistics?Bjørn Kjos-Hanssen, Antoine Taveneaux & Neil Thapen - 2014 - Annals of Pure and Applied Logic 165 (9):1470-1483.
    In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle. The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ. While the Hippocratic approach is in general much more restrictive, there are cases where the two coincide. (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12.  8
    The Polynomial and Linear Time Hierarchies in V0.Leszek A. Kołodziejczyk & Neil Thapen - 2009 - Mathematical Logic Quarterly 55 (5):509-514.
    We show that the bounded arithmetic theory V0 does not prove that the polynomial time hierarchy collapses to the linear time hierarchy . The result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input; we derive this from a theorem of Ajtai.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  13.  10
    University of California at Berkeley Berkeley, CA, USA March 24–27, 2011.G. Aldo Antonelli, Laurent Bienvenu, Lou van den Dries, Deirdre Haskell, Justin Moore, Christian Rosendal Uic, Neil Thapen & Simon Thomas - 2012 - Bulletin of Symbolic Logic 18 (2).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  14.  6
    Cobham Recursive Set Functions.Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller & Neil Thapen - 2016 - Annals of Pure and Applied Logic 167 (3):335-369.