# zbMATH — the first resource for mathematics

## Cook, Stephen Arthur

Compute Distance To:
 Author ID: cook.stephen-a Published as: Cook, Stephen A.; Cook, Stephen; Cook, S. A.; Cook, S. External Links: MGP · Wikidata · dblp · GND · IdRef Awards: Turing Award (1982)
 Documents Indexed: 100 Publications since 1966, including 3 Books
all top 5

#### Co-Authors

 29 single-authored 5 Borodin, Allan B. 5 McKenzie, Pierre 5 Pitassi, Toniann 4 Beame, Paul W. 4 Braverman, Mark 4 Reckhow, Robert A. 3 Dymond, Patrick W. 3 Edmonds, Jeff A. 3 Fontes, Lila 3 Hoover, H. James 3 Impagliazzo, Russell 3 Lê, Dai Tri Man 3 Santhanam, Rahul 3 Wehr, Dustin 2 Aanderaa, Stål O. 2 Aehlig, Klaus 2 Kapron, Bruce M. 2 Kawamura, Akitoshi 2 Oppen, Derek C. 2 Sethi, Ravi 2 Soltys, Michael 2 Urquhart, Alasdair 1 Ada, Anil 1 Agarwal, Pankaj Kumar 1 Bellantoni, Stephen J. 1 Budd, Christopher John 1 Chattopadhyay, Arkadev 1 Dwork, Cynthia 1 Filmus, Yuval 1 Ghasemloo, Kaveh 1 Gupta, Arvind Kumar 1 Haken, Armin 1 Hill, Adrian T. 1 Hussmann, Heinrich 1 Jézéquel, Jean-Marc 1 Kolokolova, Antonina 1 Koucký, Michal 1 Krajíček, Jan 1 Liu, Yongmei 1 Medabalimi, Venkatesh 1 Mehlhorn, Kurt 1 Melvin, Thomas R. O. 1 Mitchell, David G. M. 1 Morioka, Tsuyoshi 1 Pachl, Jan K. 1 Pippenger, Nicholas J. 1 Pressman, Irwin S. 1 Rackoff, Charles W. 1 Ramachandran, Vijaya 1 Reischuk, Rüdiger 1 Rodríguez, Daniel J. 1 Ruzzo, Walter L. 1 Satpathy, Manoranjan 1 Siebel, Nils T. 1 Thapen, Neil 1 Tompa, Martin 1 Tzameret, Iddo 1 Verbeek, Rutger 1 von Braunmühl, Burchard 1 Wang, Hao 1 Yamakami, Tomoyuki 1 Ye, Yuli
all top 5

#### Serials

 12 SIAM Journal on Computing 7 Journal of Computer and System Sciences 4 ACM Transactions on Computation Theory 3 Information and Control 3 Kiberneticheskiĭ Sbornik. Novaya Seriya 3 Annals of Pure and Applied Logic 3 Computational Complexity 3 Logical Methods in Computer Science 2 Information Processing Letters 2 Journal of the Association for Computing Machinery 2 The Journal of Symbolic Logic 2 Information and Computation 2 ACM Transactions on Computational Logic 2 Perspectives in Logic 1 Mathematische Annalen 1 Transactions of the American Mathematical Society 1 Bulletin of the Section of Logic 1 Journal of Algorithms 1 Applied Numerical Mathematics 1 Journal of Logic and Computation 1 Communications of the ACM 1 L’Enseignement Mathématique. 2e Série 1 Pokroky Matematiky, Fyziky & Astronomie 1 Notices of the American Mathematical Society 1 Distributed Computing 1 Archive for Mathematical Logic 1 International Journal of Modern Physics D 1 Journal of the ACM 1 Journal of Software Maintenance and Evolution. Research and Practice 1 Lecture Notes in Computer Science
all top 5

#### Fields

 87 Computer science (68-XX) 42 Mathematical logic and foundations (03-XX) 7 Information and communication theory, circuits (94-XX) 5 Combinatorics (05-XX) 5 Linear and multilinear algebra; matrix theory (15-XX) 3 Numerical analysis (65-XX) 1 General and overarching topics; collections (00-XX) 1 Associative rings and algebras (16-XX) 1 Group theory and generalizations (20-XX) 1 Measure and integration (28-XX) 1 Partial differential equations (35-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Differential geometry (53-XX) 1 Probability theory and stochastic processes (60-XX) 1 Relativity and gravitational theory (83-XX) 1 Geophysics (86-XX) 1 Operations research, mathematical programming (90-XX) 1 Game theory, economics, finance, and other social and behavioral sciences (91-XX)

#### Citations contained in zbMATH Open

84 Publications have been cited 1,999 times in 1,586 Documents Cited by Year
The relative efficiency of propositional proof systems. Zbl 0408.03044
Cook, Stephen A.; Reckhow, Robert A.
1979
The complexity of theorem-proving procedures. Zbl 0253.68020
Cook, Stephen A.
1971
A taxonomy of problems with fast parallel algorithms. Zbl 0575.68045
Cook, Stephen A.
1985
The complexity of theorem-proving procedures. Zbl 0363.68125
Cook, S. A.
1975
Characterizations of pushdown machines in terms of time-bounded computers. Zbl 0222.02035
Cook, Stephen A.
1971
A new recursion-theoretic characterization of the polytime functions. Zbl 0766.68037
Bellantoni, Stephen; Cook, Stephen
1992
Soundness and completeness of an axiom system for program verification. Zbl 0374.68009
Cook, Stephen A.
1978
Upper and lower time bounds for parallel random access machines without simultaneous writes. Zbl 0591.68049
Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger
1986
Time bounded random access machines. Zbl 0284.68038
Cook, Stephen A.; Reckhow, Robert A.
1973
An observation on time-storage trade off. Zbl 0306.68026
Cook, Stephen A.
1974
Log depth circuits for division and related problems. Zbl 0619.68047
Beame, Paul W.; Cook, Stephen A.; Hoover, H. James
1986
Feasibly constructive proofs and the propositional calculus. Zbl 0357.68061
Cook, Stephen A.
1975
Logical foundations of proof complexity. Zbl 1206.03051
Cook, Stephen; Nguyen, Phuong
2010
Parallel computation for well-endowed rings and space-bounded probabilistic machines. Zbl 0598.68043
Borodin, A.; Cook, S.; Pippenger, N.
1983
Problems complete for deterministic logarithmic space. Zbl 0644.68058
Cook, Stephen A.; McKenzie, Pierre
1987
Functional interpretations of feasibly constructive arithmetic. Zbl 0780.03026
Cook, Stephen; Urquhart, Alasdair
1993
A time-space tradeoff for sorting on a general sequential model of computation. Zbl 0478.68061
Borodin, A.; Cook, S.
1982
On the lengths of proofs in the propositional calculus. Preliminary version. Zbl 0375.02004
Cook, Stephen; Reckhow, Robert
1974
Finding hard instances of the satisfiability problem: A survey. Zbl 0889.68073
Cook, Stephen A.; Mitchell, David G.
1997
A hierarchy for nondeterministic time complexity. Zbl 0278.68042
Cook, Stephen A.
1973
Space lower bounds for maze threadability on restricted machines. Zbl 0445.68038
Cook, Stephen A.; Rackoff, Charles W.
1980
Two applications of inductive counting for complementation problems. Zbl 0678.68031
Borodin, Allan; Cook, Stephen A.; Dymond, Patrick W.; Ruzzos, Walter L.; Tompa, Martin
1989
An optimal parallel algorithm for formula evaluation. Zbl 0825.68424
Buss, S.; Cook, S.; Gupta, Arvind; Ramachandran, V.
1992
Computing over the reals: foundations for scientific computing. Zbl 1092.68038
Braverman, Mark; Cook, Stephen
2006
The relative complexity of NP search problems. Zbl 0920.68051
Beame, Paul; Cook, Stephen; Edmonds, Jeff; Impagliazzo, Russell; Pitassi, Toniann
1998
A new characterization of type-2 feasibility. Zbl 0843.68028
Kapron, B. M.; Cook, S. A.
1996
Towards a complexity theory of synchronous parallel computation. Zbl 0473.68041
Cook, Stephen A.
1981
Short propositional formulas represent nondeterministic computations. Zbl 0633.68034
Cook, Stephen A.
1988
On the minimum computation time of functions. Zbl 0188.33402
Cook, S. A.; Aanderaa, Stål O.
1969
Storage requirements for deterministic polynomial time recognizable languages. Zbl 0337.68031
Cook, Stephen; Sethi, Ravi
1976
On the number of additions to compute specific polynomials. Zbl 0341.65034
Borodin, Allan; Cook, Stephen
1976
Characterizations for the basic feasible functionals of finite type. Zbl 0788.03068
Cook, Stephen A.; Kapron, Bruce M.
1990
Computability and complexity of higher type functions. Zbl 0757.03021
Cook, Stephen A.
1992
The relative complexity of NP search problems. Zbl 0978.68526
Beame, Paul; Cook, Stephen; Edmonds, Jeff; Impagliazzo, Russell; Pitassi, Toniann
1995
Consequences of the provability of $$\mathrm{NP}\subseteq \mathrm{P/poly}$$. Zbl 1133.03035
Cook, Stephen; Krajíček, Jan
2007
Complexity theory for operators in analysis. Zbl 1322.68083
Kawamura, Akitoshi; Cook, Stephen
2012
The P versus NP problem. Zbl 1194.68001
Cook, Stephen
2006
Quantified propositional calculus and a second-order theory for NC$$^{\text \textbf{1}}$$. Zbl 1090.03029
Cook, Stephen; Morioka, Tsuyoshi
2005
Time-bounded random access machines. Zbl 0357.68055
Cook, Stephen A.; Reckhow, Robert A.
1972
The proof complexity of linear algebra. Zbl 1059.03064
Soltys, Michael; Cook, Stephen
2004
An overview of computational complexity. Zbl 0622.68039
Cook, Stephen A.
1983
Logical foundations of proof complexity. Reprint of the 2010 hardback ed. Zbl 1284.03001
Cook, Stephen; Nguyen, Phuong
2014
An observation on time-storage trade off. Zbl 0305.68066
Cook, Stephen A.
1973
Theories for complexity classes and their propositional translations. Zbl 1084.03044
Cook, Stephen
2004
The parallel complexity of abelian permutation group problems. Zbl 0647.68045
McKenzie, Pierre; Cook, Stephen A.
1987
The classification of problems which have fast parallel algorithms. Zbl 0529.68014
Cook, Stephen A.
1983
The strength of replacement in weak arithmetic. Zbl 1407.03075
Cook, Stephen; Thapen, Neil
2006
Complexity theory of parallel time and hardware. Zbl 0666.68045
Dymond, Patrick W.; Cook, Stephen A.
1989
Linear time simulation of deterministic two-way pushdown automata. Zbl 0255.68015
Cook, Stephen A.
1972
The hardness of being private. Zbl 1321.94032
2014
A tight relationship between generic oracles and type-2 complexity theory. Zbl 0881.68051
Cook, Stephen; Impagliazzo, Russell; Yamakami, Tomoyuki
1997
An exponential lower bound for the size of monotone real circuits. Zbl 0922.68065
Haken, Armin; Cook, Stephen A.
1999
Corrigendum to “Soundness and completeness of an axiom system for program verification”. Zbl 0466.68015
Cook, Stephen A.
1981
Functional interpretations of feasibly constructive arithmetic. Abstract. Zbl 0776.03028
Cook, Stephen; Urquhart, Alasdair
1990
Complexity theory for operators in analysis. Zbl 1293.68134
Kawamura, Akitoshi; Cook, Stephen
2010
Theories for TC$$^0$$ and other small complexity classes. Zbl 1126.68048
Nguyen, Phuong; Cook, Stephen
2006
A depth-universal circuit. Zbl 0573.94015
Cook, Stephen A.; Hoover, H. James
1985
Relating the provable collapse of $$\mathbf P$$ to $$\mathbf N\mathbf C^1$$ and the power of logical theories. Zbl 0892.03024
Cook, Stephen
1998
The solvability of the derivability problem for one-normal systems. Zbl 0207.31204
Cook, S. A.
1966
Boolean programs and quantified propositional proof systems. Zbl 0951.03052
Cook, Stephen; Soltys, Michael
1999
Log depth circuits for division and related problems. Zbl 0797.68074
Beame, Paul W.; Cook, Stephen A.; Hoover, H. James
1986
Storage requirements for deterministic polynomial time recognizable languages. Zbl 0412.68078
Cook, Stephen; Sethi, Ravi
1974
A complete axiomatization for Blocks World. Zbl 1046.68101
Cook, Stephen A.; Liu, Yongmei
2003
Computational complexity of higher type functions. Zbl 0749.03031
Cook, Stephen A.
1991
The recognition of deterministic CFLs in small time and space. Zbl 0535.68023
von Braunmühl, Burchard; Cook, Stephen; Mehlhorn, Kurt; Verbeek, Rutger
1983
Variations on pushdown machines (detailed abstract). Zbl 1282.68103
Cook, Stephen A.
1969
Relativizing small complexity classes and their theories. Zbl 1179.68059
Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong
2007
Lower bounds for nondeterministic semantic read-once branching programs. Zbl 1388.68028
Cook, Stephen; Edmonds, Jeff; Medabalimi, Venkatesh; Pitassi, Toniann
2016
Parallel pointer machines. Zbl 0781.68052
Cook, Stephen A.; Dymond, Patrick W.
1993
A second-order system for polytime reasoning based on Grädel’s theorem. Zbl 1036.03042
Cook, Stephen; Kolokolova, Antonina
2003
On the minimum computation time of functions. Zbl 0231.02047
Cook, S. A.; Aanderaa, Stål O.
1971
Characterizations of pushdown machines in terms of time-bounded computers. Zbl 0289.02021
Cook, S. A.
1974
Towards a complexity theory of synchronous parallel computation. Zbl 0484.68036
Cook, Stephen A.
1982
A feasibly constructive lower bound for resolution proofs. Zbl 0702.68065
Cook, Stephen; Pitassi, Toniann
1990
Proving assertions about programs that manipulate data structures. Zbl 0359.68011
Oppen, Derek C.; Cook, Stephen A.
1975
A hierarchy for nondeterministic time complexity. Zbl 0361.68074
Cook, Stephen A.
1972
An assertion language for data structures. Zbl 0382.68017
Cook, Stephen A.; Oppen, Derek C.
1975
A formal theory for the complexity class associated with the stable marriage problem. Zbl 1247.68095
Lê, Dai Tri Man; Cook, Stephen A.; Ye, Yuli
2011
The importance of the P versus NP question. Zbl 1326.68140
Cook, Stephen
2003
The complexity of the comparator circuit value problem. Zbl 1347.68156
Cook, Stephen A.; Filmus, Yuval; Lê, Dai Tri Man
2014
Relativizing small complexity classes and their theories. Zbl 1336.68084
Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong
2016
Branching programs for tree evaluation. Zbl 1250.68106
Braverman, Mark; Cook, Stephen; McKenzie, Pierre; Santhanam, Rahul; Wehr, Dustin
2009
Formal theories for linear algebra. Zbl 1238.03020
Cook, Stephen; Fontes, Lila
2012
Formal theories for linear algebra. Zbl 1238.03019
Cook, Stephen; Fontes, Lila
2010
Lower bounds for nondeterministic semantic read-once branching programs. Zbl 1388.68028
Cook, Stephen; Edmonds, Jeff; Medabalimi, Venkatesh; Pitassi, Toniann
2016
Relativizing small complexity classes and their theories. Zbl 1336.68084
Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong
2016
Logical foundations of proof complexity. Reprint of the 2010 hardback ed. Zbl 1284.03001
Cook, Stephen; Nguyen, Phuong
2014
The hardness of being private. Zbl 1321.94032
2014
The complexity of the comparator circuit value problem. Zbl 1347.68156
Cook, Stephen A.; Filmus, Yuval; Lê, Dai Tri Man
2014
Complexity theory for operators in analysis. Zbl 1322.68083
Kawamura, Akitoshi; Cook, Stephen
2012
Formal theories for linear algebra. Zbl 1238.03020
Cook, Stephen; Fontes, Lila
2012
A formal theory for the complexity class associated with the stable marriage problem. Zbl 1247.68095
Lê, Dai Tri Man; Cook, Stephen A.; Ye, Yuli
2011
Logical foundations of proof complexity. Zbl 1206.03051
Cook, Stephen; Nguyen, Phuong
2010
Complexity theory for operators in analysis. Zbl 1293.68134
Kawamura, Akitoshi; Cook, Stephen
2010
Formal theories for linear algebra. Zbl 1238.03019
Cook, Stephen; Fontes, Lila
2010
Branching programs for tree evaluation. Zbl 1250.68106
Braverman, Mark; Cook, Stephen; McKenzie, Pierre; Santhanam, Rahul; Wehr, Dustin
2009
Consequences of the provability of $$\mathrm{NP}\subseteq \mathrm{P/poly}$$. Zbl 1133.03035
Cook, Stephen; Krajíček, Jan
2007
Relativizing small complexity classes and their theories. Zbl 1179.68059
Aehlig, Klaus; Cook, Stephen; Nguyen, Phuong
2007
Computing over the reals: foundations for scientific computing. Zbl 1092.68038
Braverman, Mark; Cook, Stephen
2006
The P versus NP problem. Zbl 1194.68001
Cook, Stephen
2006
The strength of replacement in weak arithmetic. Zbl 1407.03075
Cook, Stephen; Thapen, Neil
2006
Theories for TC$$^0$$ and other small complexity classes. Zbl 1126.68048
Nguyen, Phuong; Cook, Stephen
2006
Quantified propositional calculus and a second-order theory for NC$$^{\text \textbf{1}}$$. Zbl 1090.03029
Cook, Stephen; Morioka, Tsuyoshi
2005
The proof complexity of linear algebra. Zbl 1059.03064
Soltys, Michael; Cook, Stephen
2004
Theories for complexity classes and their propositional translations. Zbl 1084.03044
Cook, Stephen
2004
A complete axiomatization for Blocks World. Zbl 1046.68101
Cook, Stephen A.; Liu, Yongmei
2003
A second-order system for polytime reasoning based on Grädel’s theorem. Zbl 1036.03042
Cook, Stephen; Kolokolova, Antonina
2003
The importance of the P versus NP question. Zbl 1326.68140
Cook, Stephen
2003
An exponential lower bound for the size of monotone real circuits. Zbl 0922.68065
Haken, Armin; Cook, Stephen A.
1999
Boolean programs and quantified propositional proof systems. Zbl 0951.03052
Cook, Stephen; Soltys, Michael
1999
The relative complexity of NP search problems. Zbl 0920.68051
Beame, Paul; Cook, Stephen; Edmonds, Jeff; Impagliazzo, Russell; Pitassi, Toniann
1998
Relating the provable collapse of $$\mathbf P$$ to $$\mathbf N\mathbf C^1$$ and the power of logical theories. Zbl 0892.03024
Cook, Stephen
1998
Finding hard instances of the satisfiability problem: A survey. Zbl 0889.68073
Cook, Stephen A.; Mitchell, David G.
1997
A tight relationship between generic oracles and type-2 complexity theory. Zbl 0881.68051
Cook, Stephen; Impagliazzo, Russell; Yamakami, Tomoyuki
1997
A new characterization of type-2 feasibility. Zbl 0843.68028
Kapron, B. M.; Cook, S. A.
1996
The relative complexity of NP search problems. Zbl 0978.68526
Beame, Paul; Cook, Stephen; Edmonds, Jeff; Impagliazzo, Russell; Pitassi, Toniann
1995
Functional interpretations of feasibly constructive arithmetic. Zbl 0780.03026
Cook, Stephen; Urquhart, Alasdair
1993
Parallel pointer machines. Zbl 0781.68052
Cook, Stephen A.; Dymond, Patrick W.
1993
A new recursion-theoretic characterization of the polytime functions. Zbl 0766.68037
Bellantoni, Stephen; Cook, Stephen
1992
An optimal parallel algorithm for formula evaluation. Zbl 0825.68424
Buss, S.; Cook, S.; Gupta, Arvind; Ramachandran, V.
1992
Computability and complexity of higher type functions. Zbl 0757.03021
Cook, Stephen A.
1992
Computational complexity of higher type functions. Zbl 0749.03031
Cook, Stephen A.
1991
Characterizations for the basic feasible functionals of finite type. Zbl 0788.03068
Cook, Stephen A.; Kapron, Bruce M.
1990
Functional interpretations of feasibly constructive arithmetic. Abstract. Zbl 0776.03028
Cook, Stephen; Urquhart, Alasdair
1990
A feasibly constructive lower bound for resolution proofs. Zbl 0702.68065
Cook, Stephen; Pitassi, Toniann
1990
Two applications of inductive counting for complementation problems. Zbl 0678.68031
Borodin, Allan; Cook, Stephen A.; Dymond, Patrick W.; Ruzzos, Walter L.; Tompa, Martin
1989
Complexity theory of parallel time and hardware. Zbl 0666.68045
Dymond, Patrick W.; Cook, Stephen A.
1989
Short propositional formulas represent nondeterministic computations. Zbl 0633.68034
Cook, Stephen A.
1988
Problems complete for deterministic logarithmic space. Zbl 0644.68058
Cook, Stephen A.; McKenzie, Pierre
1987
The parallel complexity of abelian permutation group problems. Zbl 0647.68045
McKenzie, Pierre; Cook, Stephen A.
1987
Upper and lower time bounds for parallel random access machines without simultaneous writes. Zbl 0591.68049
Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger
1986
Log depth circuits for division and related problems. Zbl 0619.68047
Beame, Paul W.; Cook, Stephen A.; Hoover, H. James
1986
Log depth circuits for division and related problems. Zbl 0797.68074
Beame, Paul W.; Cook, Stephen A.; Hoover, H. James
1986
A taxonomy of problems with fast parallel algorithms. Zbl 0575.68045
Cook, Stephen A.
1985
A depth-universal circuit. Zbl 0573.94015
Cook, Stephen A.; Hoover, H. James
1985
Parallel computation for well-endowed rings and space-bounded probabilistic machines. Zbl 0598.68043
Borodin, A.; Cook, S.; Pippenger, N.
1983
An overview of computational complexity. Zbl 0622.68039
Cook, Stephen A.
1983
The classification of problems which have fast parallel algorithms. Zbl 0529.68014
Cook, Stephen A.
1983
The recognition of deterministic CFLs in small time and space. Zbl 0535.68023
von Braunmühl, Burchard; Cook, Stephen; Mehlhorn, Kurt; Verbeek, Rutger
1983
A time-space tradeoff for sorting on a general sequential model of computation. Zbl 0478.68061
Borodin, A.; Cook, S.
1982
Towards a complexity theory of synchronous parallel computation. Zbl 0484.68036
Cook, Stephen A.
1982
Towards a complexity theory of synchronous parallel computation. Zbl 0473.68041
Cook, Stephen A.
1981
Corrigendum to “Soundness and completeness of an axiom system for program verification”. Zbl 0466.68015
Cook, Stephen A.
1981
Space lower bounds for maze threadability on restricted machines. Zbl 0445.68038
Cook, Stephen A.; Rackoff, Charles W.
1980
The relative efficiency of propositional proof systems. Zbl 0408.03044
Cook, Stephen A.; Reckhow, Robert A.
1979
Soundness and completeness of an axiom system for program verification. Zbl 0374.68009
Cook, Stephen A.
1978
Storage requirements for deterministic polynomial time recognizable languages. Zbl 0337.68031
Cook, Stephen; Sethi, Ravi
1976
On the number of additions to compute specific polynomials. Zbl 0341.65034
Borodin, Allan; Cook, Stephen
1976
The complexity of theorem-proving procedures. Zbl 0363.68125
Cook, S. A.
1975
Feasibly constructive proofs and the propositional calculus. Zbl 0357.68061
Cook, Stephen A.
1975
Proving assertions about programs that manipulate data structures. Zbl 0359.68011
Oppen, Derek C.; Cook, Stephen A.
1975
An assertion language for data structures. Zbl 0382.68017
Cook, Stephen A.; Oppen, Derek C.
1975
An observation on time-storage trade off. Zbl 0306.68026
Cook, Stephen A.
1974
On the lengths of proofs in the propositional calculus. Preliminary version. Zbl 0375.02004
Cook, Stephen; Reckhow, Robert
1974
Storage requirements for deterministic polynomial time recognizable languages. Zbl 0412.68078
Cook, Stephen; Sethi, Ravi
1974
Characterizations of pushdown machines in terms of time-bounded computers. Zbl 0289.02021
Cook, S. A.
1974
Time bounded random access machines. Zbl 0284.68038
Cook, Stephen A.; Reckhow, Robert A.
1973
A hierarchy for nondeterministic time complexity. Zbl 0278.68042
Cook, Stephen A.
1973
An observation on time-storage trade off. Zbl 0305.68066
Cook, Stephen A.
1973
Time-bounded random access machines. Zbl 0357.68055
Cook, Stephen A.; Reckhow, Robert A.
1972
Linear time simulation of deterministic two-way pushdown automata. Zbl 0255.68015
Cook, Stephen A.
1972
A hierarchy for nondeterministic time complexity. Zbl 0361.68074
Cook, Stephen A.
1972
The complexity of theorem-proving procedures. Zbl 0253.68020
Cook, Stephen A.
1971
Characterizations of pushdown machines in terms of time-bounded computers. Zbl 0222.02035
Cook, Stephen A.
1971
On the minimum computation time of functions. Zbl 0231.02047
Cook, S. A.; Aanderaa, Stål O.
1971
On the minimum computation time of functions. Zbl 0188.33402
Cook, S. A.; Aanderaa, Stål O.
1969
Variations on pushdown machines (detailed abstract). Zbl 1282.68103
Cook, Stephen A.
1969
The solvability of the derivability problem for one-normal systems. Zbl 0207.31204
Cook, S. A.
1966
all top 5

#### Cited by 1,887 Authors

 24 Beyersdorff, Olaf 22 Krajíček, Jan 17 Cook, Stephen Arthur 16 Buss, Samuel R. 15 Allender, Eric W. 14 McKenzie, Pierre 13 Pitassi, Toniann 13 Pudlák, Pavel 12 Ibarra, Oscar H. 11 Bergstra, Jan A. 11 Dal Lago, Ugo 10 Buss, Sam 10 Jeřábek, Emil 10 Thapen, Neil 9 Huynh, Dung T. 9 Karpinski, Marek 9 Mahajan, Meena 9 Müller, Moritz 8 Hofmann, Martin 8 Jenner, Birgit 8 Köbler, Johannes 8 Mix Barrington, David A. 8 Stewart, Iain A. 7 Beame, Paul W. 7 Book, Ronald Vernon 7 Galesi, Nicola 7 Lauria, Massimo 7 Lutz, Jack H. 7 Niggl, Karl-Heinz 7 Papadimitriou, Christos Harilaos 7 Soltys, Michael 7 Tompa, Martin 7 Tucker, John V. 7 Tzameret, Iddo 7 Vollmer, Heribert 6 Baillot, Patrick 6 Bonet, Maria Luisa 6 Borodin, Allan B. 6 Dymond, Patrick W. 6 Engelfriet, Joost 6 Fortnow, Lance J. 6 Goldwurm, Massimiliano 6 Impagliazzo, Russell 6 Itsykson, Dmitry M. 6 Kleine Büning, Hans 6 Krebs, Andreas 6 Lange, Klaus-Jörn 6 Limaye, Nutan 6 Monien, Burkhard 6 Nordström, Jakob 6 Ruzzo, Walter L. 6 Santhanam, Rahul 6 Sarma M. N., Jayalal 6 Selman, Alan L. 6 Steinberg, Florian 6 Sudborough, Ivan Hal 6 Thérien, Denis 6 Ziegler, Martin 5 Apt, Krzysztof Rafal 5 Atserias, Albert 5 Bellantoni, Stephen J. 5 Bertoni, Alberto 5 Blinkhorn, Joshua 5 Boros, Endre 5 Buhrman, Harry 5 Clote, Peter G. 5 Das, Anupam 5 Gál, Anna 5 Grigor’ev, Dmitriĭ Yur’evich 5 Hirsch, Edward A. 5 Jones, Neil D. 5 Kawamura, Akitoshi 5 Kutyłowski, Mirosław 5 Leivant, Daniel M. 5 Litow, Bruce E. 5 Marion, Jean-Yves 5 Mayordomo, Elvira 5 Miyano, Satoru 5 Mohar, Bojan 5 Raman, Venkatesh 5 Ravikumar, Bala 5 Savitch, Walter J. 5 Stockmeyer, Larry J. 5 Straßburger, Lutz 5 Subramani, Krishnan 5 Szeider, Stefan 5 Thierauf, Thomas 5 Urquhart, Alasdair 5 Wainer, Stanley Scott 5 Zecchina, Riccardo 5 Zhang, Liyu 5 Zhang, Wenhui 4 Àlvarez, Carme 4 Arai, Noriko H. 4 Avanzini, Martin 4 Beckmann, Arnold 4 Braverman, Mark 4 Bruschi, Danilo 4 Creignou, Nadia 4 Dahlhaus, Elias ...and 1,787 more Authors
all top 5

#### Cited in 179 Serials

 262 Theoretical Computer Science 158 Journal of Computer and System Sciences 96 Information Processing Letters 92 Information and Computation 62 Annals of Pure and Applied Logic 46 Mathematical Systems Theory 42 Discrete Applied Mathematics 38 Theory of Computing Systems 37 Computational Complexity 28 The Journal of Symbolic Logic 27 Archive for Mathematical Logic 25 Annals of Mathematics and Artificial Intelligence 24 Acta Informatica 24 Artificial Intelligence 23 Algorithmica 20 Logical Methods in Computer Science 17 Journal of Automated Reasoning 15 The Bulletin of Symbolic Logic 13 European Journal of Operational Research 12 SIAM Journal on Computing 11 Journal of Symbolic Computation 9 BIT 9 Information Sciences 9 Operations Research Letters 9 Combinatorica 9 Journal of Complexity 9 MSCS. Mathematical Structures in Computer Science 9 International Journal of Foundations of Computer Science 9 RAIRO. Informatique Théorique et Applications 9 ACM Transactions on Computational Logic 8 Mathematical Logic Quarterly (MLQ) 8 RAIRO. Theoretical Informatics and Applications 7 Journal of Soviet Mathematics 6 Computing 6 RAIRO, Informatique Théorique 6 Journal of Computer Science and Technology 6 International Journal of Computer Mathematics 6 Distributed Computing 6 Prikladnaya Diskretnaya Matematika 5 Computers & Mathematics with Applications 5 Discrete Mathematics 5 Mathematical Programming 5 Studia Logica 5 Journal of Cryptology 5 Formal Aspects of Computing 5 Random Structures & Algorithms 4 Cybernetics 4 Discrete & Computational Geometry 4 International Journal of Parallel Programming 4 Annals of Operations Research 4 International Journal of Algebra and Computation 4 Journal of Mathematical Sciences (New York) 4 Philosophical Transactions of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences 4 Quantum Information Processing 4 Journal of Discrete Algorithms 3 Journal of Philosophical Logic 3 Synthese 3 SIAM Journal on Algebraic and Discrete Methods 3 Order 3 Mathematical and Computer Modelling 3 Computational Geometry 3 Journal of the ACM 3 The Review of Symbolic Logic 2 Journal of Statistical Physics 2 Mathematics of Computation 2 Chaos, Solitons and Fractals 2 Automatica 2 Calcolo 2 Journal of Pure and Applied Algebra 2 Mathematica Slovaca 2 Transactions of the American Mathematical Society 2 Science of Computer Programming 2 International Journal of Approximate Reasoning 2 Journal of the American Mathematical Society 2 Journal of Global Optimization 2 Games and Economic Behavior 2 Linear Algebra and its Applications 2 Bulletin of the American Mathematical Society. New Series 2 Mathematical Programming. Series A. Series B 2 Parallel Algorithms and Applications 2 Journal of Combinatorial Optimization 2 Chicago Journal of Theoretical Computer Science 2 The Journal of Logic and Algebraic Programming 2 Theory and Practice of Logic Programming 2 Natural Computing 2 Discrete Optimization 2 Science China. Information Sciences 2 Statistics and Computing 2 Frontiers of Computer Science 2 Computability 2 Computer Science Review 2 ACM Transactions on Computation Theory 1 Archiv für Mathematische Logik und Grundlagenforschung 1 International Journal of General Systems 1 International Journal of Theoretical Physics 1 Journal of the Franklin Institute 1 Journal of Mathematical Analysis and Applications 1 Mathematical Notes 1 Bulletin of Mathematical Biology 1 Bulletin of the Polish Academy of Sciences. Technical Sciences ...and 79 more Serials
all top 5

#### Cited in 41 Fields

 1,312 Computer science (68-XX) 558 Mathematical logic and foundations (03-XX) 113 Combinatorics (05-XX) 88 Information and communication theory, circuits (94-XX) 79 Operations research, mathematical programming (90-XX) 38 Numerical analysis (65-XX) 35 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 24 Order, lattices, ordered algebraic structures (06-XX) 21 Number theory (11-XX) 19 Quantum theory (81-XX) 18 Group theory and generalizations (20-XX) 16 Linear and multilinear algebra; matrix theory (15-XX) 13 General and overarching topics; collections (00-XX) 13 Field theory and polynomials (12-XX) 8 Algebraic geometry (14-XX) 8 Probability theory and stochastic processes (60-XX) 8 Biology and other natural sciences (92-XX) 6 Category theory; homological algebra (18-XX) 6 Measure and integration (28-XX) 6 Systems theory; control (93-XX) 5 General algebraic systems (08-XX) 5 Convex and discrete geometry (52-XX) 4 Commutative algebra (13-XX) 4 Ordinary differential equations (34-XX) 4 Dynamical systems and ergodic theory (37-XX) 4 Statistical mechanics, structure of matter (82-XX) 3 History and biography (01-XX) 3 Manifolds and cell complexes (57-XX) 3 Statistics (62-XX) 2 Associative rings and algebras (16-XX) 2 Real functions (26-XX) 2 Functions of a complex variable (30-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 1 Potential theory (31-XX) 1 Partial differential equations (35-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Geometry (51-XX) 1 General topology (54-XX) 1 Mechanics of particles and systems (70-XX) 1 Fluid mechanics (76-XX) 1 Relativity and gravitational theory (83-XX)

#### Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.