Switch to: References

Add citations

You must login to add citations.
  1. Examining fragments of the quantified propositional calculus.Steven Perron - 2008 - Journal of Symbolic Logic 73 (3):1051-1080.
    When restricted to proving $\Sigma _{i}^{q}$ formulas, the quantified propositional proof system $G_{i}^{\ast}$ is closely related to the $\Sigma _{i}^{b}$ theorems of Buss's theory $S_{2}^{i}$ . Namely, $G_{i}^{\ast}$ has polynomial-size proofs of the translations of theorems of $S_{2}^{i}$ , and $S_{2}^{i}$ proves that $G_{i}^{\ast}$ is sound. However, little is known about $G_{i}^{\ast}$ when proving more complex formulas. In this paper, we prove a witnessing theorem for $G_{i}^{\ast}$ similar in style to the KPT witnessing theorem for $T_{2}^{i}$ . This witnessing theorem (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  • The equivalence of theories that characterize ALogTime.Phuong Nguyen - 2009 - Archive for Mathematical Logic 48 (6):523-549.
    A number of theories have been developed to characterize ALogTime (or uniform NC 1, or just NC 1), the class of languages accepted by alternating logtime Turing machines, in the same way that Buss’s theory ${{\bf S}^{1}_{2}}$ characterizes polytime functions. Among these, ALV′ (by Clote) is particularly interesting because it is developed based on Barrington’s theorem that the word problem for the permutation group S 5 is complete for ALogTime. On the other hand, ALV (by Clote), T 0 NC 0 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Simulating non-prenex cuts in quantified propositional calculus.Emil Jeřábek & Phuong Nguyen - 2011 - Mathematical Logic Quarterly 57 (5):524-532.
    We show that the quantified propositional proof systems Gi are polynomially equivalent to their restricted versions that require all cut formulas to be prenex Σqi . Previously this was known only for the treelike systems G*i. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • On theories of bounded arithmetic for NC 1.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):322-340.
    We develop an arithmetical theory and its variant , corresponding to “slightly nonuniform” . Our theories sit between and , and allow evaluation of log-depth bounded fan-in circuits under limited conditions. Propositional translations of -formulas provable in admit L-uniform polynomial-size Frege proofs.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
    We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC^1 (corresponding to the “NC^1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC^1 . This in turn implies that every proof in Gentzen's sequent calculus LK of a (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation