Switch to: References

Add citations

You must login to add citations.
  1. Quantified Propositional Calculus and a Second-Order Theory for NC1.Stephen Cook & Tsuyoshi Morioka - 2005 - Archive for Mathematical Logic 44 (6):711-749.
    Let H be a proof system for quantified propositional calculus. We define the Σqj-witnessing problem for H to be: given a prenex Σqj-formula A, an H-proof of A, and a truth assignment to the free variables in A, find a witness for the outermost existential quantifiers in A. We point out that the Σq1-witnessing problems for the systems G*1and G1 are complete for polynomial time and PLS, respectively. We introduce and study the systems G*0 and G0, in which cuts are (...)
    Direct download (6 more)  
    Export citation  
    Bookmark   6 citations  
  • 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