22 found
Order:
Disambiguations
Stephen Cook [13]Stephen A. Cook [8]Stephen L. Cook [4]
  1.  99
    The Relative Efficiency of Propositional Proof Systems.Stephen A. Cook & Robert A. Reckhow - 1979 - Journal of Symbolic Logic 44 (1):36-50.
  2.  10
    Functional Interpretations of Feasibly Constructive Arithmetic.Stephen Cook & Alasdair Urquhart - 1993 - Annals of Pure and Applied Logic 63 (2):103-200.
    A notion of feasible function of finite type based on the typed lambda calculus is introduced which generalizes the familiar type 1 polynomial-time functions. An intuitionistic theory IPVω is presented for reasoning about these functions. Interpretations for IPVω are developed both in the style of Kreisel's modified realizability and Gödel's Dialectica interpretation. Applications include alternative proofs for Buss's results concerning the classical first-order system S12 and its intuitionistic counterpart IS12 as well as proofs of some of Buss's conjectures concerning IS12, (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   30 citations  
  3.  67
    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  
  4.  23
    Consequences of the Provability of NP ⊆ P/Poly.Stephen Cook & Jan Krajíček - 2007 - Journal of Symbolic Logic 72 (4):1353 - 1371.
    We prove the following results: (i) PV proves NP ⊆ P/poly iff PV proves coNP ⊆ NP/O(1). (ii) If PV proves NP ⊆ P/poly then PV proves that the Polynomial Hierarchy collapses to the Boolean Hierarchy. (iii) $S_{2}^{1}$ proves NP ⊆ P/poly iff $S_{2}^{1}$ proves coNP ⊆ NP/O(log n). (iv) If $S_{2}^{1}$ proves NP ⊆ P/poly then $S_{2}^{1}$ proves that the Polynomial Hierarchy collapses to PNP[log n]. (v) If $S_{2}^{2}$ proves NP ⊆ P/poly then $S_{2}^{2}$ proves that the Polynomial Hierarchy (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  5.  4
    The Proof Complexity of Linear Algebra.Michael Soltys & Stephen Cook - 2004 - Annals of Pure and Applied Logic 130 (1-3):277-323.
    We introduce three formal theories of increasing strength for linear algebra in order to study the complexity of the concepts needed to prove the basic theorems of the subject. We give what is apparently the first feasible proofs of the Cayley–Hamilton theorem and other properties of the determinant, and study the propositional proof complexity of matrix identities such as AB=I→BA=I.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  6.  15
    A Second-Order System for Polytime Reasoning Based on Grädel's Theorem.Stephen Cook & Antonina Kolokolova - 2003 - Annals of Pure and Applied Logic 124 (1-3):193-231.
    We introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomial-time reasoning, based on Grädel's 35) second-order Horn characterization of P. Our system has comprehension over P predicates , and only finitely many function symbols. Other systems of polynomial-time reasoning either allow induction on NP predicates , and hence are more powerful than our system , or use Cobham's theorem to introduce function symbols for all polynomial-time functions . We prove that our system is equivalent to QPV and Zambella's P-def. (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  7.  51
    Review: Alan Cobham, Yehoshua Bar-Hillel, The Intrinsic Computational Difficulty of Functions. [REVIEW]Stephen A. Cook - 1969 - Journal of Symbolic Logic 34 (4):657-657.
  8.  8
    Boolean Programs and Quantified Propositional Proof Systems.Stephen Cook & Michael Soltys - 1999 - Bulletin of the Section of Logic 28 (3):119-129.
  9.  11
    2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium'02.Lev D. Beklemishev, Stephen Cook, Olivier Lessmann, Simon Thomas, Jeremy Avigad, Arnold Beckmann, Tim Carlson, Robert L. Constable & Kosta Došen - 2003 - Bulletin of Symbolic Logic 9 (1):71.
  10. 2008 Annual Meeting of the Association for Symbolic Logic-University of California, Irvine-Irvine, California-March 27-30, 2008-Abstracts. [REVIEW]Sam Buss, Stephen Cook, Jos Ferreirs, Andy Lewis, David Marker, Theodore Slaman & Jamie Tappenden - 2008 - Bulletin of Symbolic Logic 14 (3).
  11.  17
    University of California, Irvine Irvine, California March 27–30, 2008.Sam Buss, Stephen Cook, José Ferreirós, David Marker, Theodore Slaman & Jamie Tappenden - 2008 - Bulletin of Symbolic Logic 14 (3).
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12.  30
    Alan Cobham. The Intrinsic Computational Difficulty of Functions. Logic, Methodology and Philosophy of Science, Proceedings of the 1964 International Congress, Edited by Yehoshua Bar-Hillel, Studies in Logic and the Foundations of Mathematics, North-Holland Publishing Company, Amsterdam1965, Pp. 24–30. [REVIEW]Stephen A. Cook - 1969 - Journal of Symbolic Logic 34 (4):657.
  13.  22
    Bečvář Jiří. Real-Time and Complexity Problems in Automata Theory. English with Czech Summary. Kybernetika , Vol. 1 , Pp. 475–498. [REVIEW]Stephen A. Cook - 1971 - Journal of Symbolic Logic 36 (2):346-346.
  14.  9
    Isaiah 14: The Birth of a Zombie Apocalypse?Stephen L. Cook - 2019 - Interpretation: A Journal of Bible and Theology 73 (2):130-142.
    Isaiah 14, a text about the infamous fall into the netherworld of a proud celestial being, has played a key role in the history of biblical understanding. In particular, the netherworld eschatology shaped Israelite end-time beliefs, or apocalyptic eschatology. In Isaiah 14, before readers’ eyes, a transcendent archetype, the ill-fated “Shining One,” materializes on earth as an historical figure, King Sargon II of Assyria. Later, the idea of an “incarnation” of the Shining One as an earthly entity evolves as a (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  24
    Jan Krajíček, Pavel Pudlák, and Gaisi Takeuti. Bounded Arithmetic and the Polynomial Hierarchy. Ibid., Vol. 52 , Pp. 143–153. - Samuel R. Buss. Relating the Bounded Arithmetic and Polynomial Time Hierarchies. Ibid., Vol. 75 , Pp. 67–77. - Domenico Zambella. Notes on Polynomially Bounded Arithmetic. The Journal of Symbolic Logic, Vol. 61 , Pp. 942–966. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
  16.  9
    Manuel Blum. A Machine-Independent Theory of the Complexity of Recursive Functions. Journal of the Association for Computing Machinery, Vol. 14 , Pp. 322–336. [REVIEW]Stephen A. Cook - 1969 - Journal of Symbolic Logic 34 (4):657-658.
  17.  8
    Review: Jiri Becvar, Real-Time and Complexity Problems in Automata Theory. [REVIEW]Stephen A. Cook - 1971 - Journal of Symbolic Logic 36 (2):346-346.
  18.  5
    Review: Jan Krajicek, Pavel Pudlak, Gaisi Takeuti, Bounded Arithmetic and the Polynomial Hierarchy; Samuel R. Buss, Relating the Bounded Arithmetic and Polynomial Time Hierarchies; Domenico Zambella, Notes on Polynomially Bounded Arithmetic. [REVIEW]Stephen Cook - 1999 - Journal of Symbolic Logic 64 (4):1821-1823.
  19.  7
    Review: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions. [REVIEW]Stephen A. Cook - 1969 - Journal of Symbolic Logic 34 (4):657-658.
  20.  9
    Social and Economic Life in Second Temple Judea by Samuel L. Adams. [REVIEW]Stephen L. Cook - 2015 - Interpretation: A Journal of Bible and Theology 69 (4):473-475.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21. The Social Roots of Biblical Yahwism.Stephen L. Cook - 2004
    No categories
     
    Export citation  
     
    Bookmark  
  22.  12
    Tag Systems and Lag Systems.Hao Wang, John Cocke, Marvin Minsky & Stephen A. Cook - 1971 - Journal of Symbolic Logic 36 (2):344-344.
    Direct download  
     
    Export citation  
     
    Bookmark