14 found
Order:
  1.  14
    Structure and Definability in General Bounded Arithmetic Theories.Chris Pollett - 1999 - Annals of Pure and Applied Logic 100 (1-3):189-245.
    The bounded arithmetic theories R2i, S2i, and T2i are closely connected with complexity theory. This paper is motivated by the questions: what are the Σi+1b-definable multifunctions of R2i? and when is one theory conservative over another? To answer these questions we consider theories , and where induction is restricted to prenex formulas. We also define which has induction up to the 0 or 1-ary L2-terms in the set τ. We show and and for . We show that the -multifunctions of (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  2.  8
    Multifunction Algebras and the Provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
    We introduce multifunction algebras B i τ where τ is a set of 0 or 1-ary terms used to bound recursion lengths. We show that if for all ℓ ∈ τ we have ℓ ∈ O then B i τ = FP Σ i−1 p , those multifunctions computable in polynomial time with at most O )) queries to a Σ i−1 p witness oracle for ℓ ∈ τ and p a polynomial. We use our algebras to obtain independence results (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  3.  7
    Arnold Beckmann. Proving Consistency of Equational Theories in Bounded Arithmetic. The Journal of Symbolic Logic, Vol. 67 , Pp. 279–296. [REVIEW]Chris Pollett - 2003 - Bulletin of Symbolic Logic 9 (1):44-45.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  4.  35
    On the Bounded Version of Hilbert's Tenth Problem.Chris Pollett - 2003 - Archive for Mathematical Logic 42 (5):469-488.
    The paper establishes lower bounds on the provability of.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  5.  13
    On the Finite Axiomatizability of ∀Σ̂1b.Chris Pollett - 2018 - Mathematical Logic Quarterly 64 (1-2):6-24.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  6.  16
    Strengths and Weaknesses of LH Arithmetic.Chris Pollett & Randall Pruim - 2002 - Mathematical Logic Quarterly 48 (2):221-243.
    In this paper we provide a new arithmetic characterization of the levels of the og-time hierarchy . We define arithmetic classes equation image and equation image that correspond to equation image-LOGTIME and equation image-LOGTIME, respectively. We break equation image and equation image into natural hierarchies of subclasses equation image and equation image. We then define bounded arithmetic deduction systems equation image′ whose equation image-definable functions are precisely B. We show these theories are quite strong in that LIOpen proves for any (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  7
    Ordinal Notations and Well-Orderings in Bounded Arithmetic.Arnold Beckmann, Chris Pollett & Samuel R. Buss - 2003 - Annals of Pure and Applied Logic 120 (1-3):197-223.
    This paper investigates provability and non-provability of well-foundedness of ordinal notations in weak theories of bounded arithmetic. We define a notion of well-foundedness on bounded domains. We show that T21 and S22 can prove the well-foundedness on bounded domains of the ordinal notations below 0 and Γ0. As a corollary, the class of polynomial local search problems, PLS, can be augmented with cost functions that take ordinal values below 0 and Γ0 without increasing the class PLS.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  7
    Ordinal Notations and Well-Orderings in Bounded Arithmetic (Vol 120, Pg 197, 2003).Arnold Beckmann, Samuel R. Buss & Chris Pollett - 2003 - Annals of Pure and Applied Logic 123 (1-3):291-291.
    This paper investigates provability and non-provability of well-foundedness of ordinal notations in weak theories of bounded arithmetic. We define a notion of well-foundedness on bounded domains. We show that T21 and S22 can prove the well-foundedness on bounded domains of the ordinal notations below 0 and Γ0. As a corollary, the class of polynomial local search problems, PLS, can be augmented with cost functions that take ordinal values below 0 and Γ0 without increasing the class PLS.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  13
    The Weak Pigeonhole Principle for Function Classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
    It is well known that S12 cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability of the surjective weak pigeonhole principle in S12 for provably weaker function classes.
    No categories
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  10.  14
    A Theory for Log-Space and NLIN Versus Co-NLIN.Chris Pollett - 2003 - Journal of Symbolic Logic 68 (4):1082-1090.
    The use of $Nepomnja\check{s}\check{c}i\check{i}'s$ Theorem in the proofs of independence results for bounded arithmetic theories is investigated. Using this result and similar ideas, it is shown that at least one of S1 or TLS does not prove the Matiyasevich-Robinson-Davis-Putnam Theorem. It is also established that TLS does not prove a statement that roughly means nondeterministic linear time is equal to co-nondeterministic linear time. Here S1 is a conservative extension of the well-studied theory IΔ0 and TLS is a theory for LOGSPACE (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark  
  11.  13
    Erratum to “Ordinal Notations and Well-Orderings in Bounded Arithmetic” [Annals of Pure and Applied Logic 120 197–223]. [REVIEW]Arnold Beckmann, Samuel R. Buss & Chris Pollett - 2003 - Annals of Pure and Applied Logic 123 (1-3):291.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12.  6
    The Journal of Symbolic Logic.Chris Pollett - 2003 - Bulletin of Symbolic Logic 9 (1):44-45.
  13.  7
    Conservative Fragments of {{S}^{1} {2}} and {{R}^{1} {2}}.Chris Pollett - 2011 - Archive for Mathematical Logic 50 (3-4):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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  14.  15
    Translating IΔ0 + Exp Proofs Into Weaker Systems.Chris Pollett - 2000 - Mathematical Logic Quarterly 46 (2):249-256.
    The purpose of this paper is to explore the relationship between IΔ0 + exp and its weaker subtheories. We give a method of translating certain classes of IΔ0 + exp proofs into weaker systems of arithmetic such as Buss' systems S2. We show if IEi ⊢ A with a proof P of expind-rank ≤ n + 1where all or have bounding terms not containing function symbols, then Si2 ⊇ IEi,2 ⊢ An. Here A is not necessarily a bounded formula. For (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation