Concepedia
Information Processing Letters · 1987 · 12 citations · 7 references
Natural SciencesComputer ScienceMathematicsDiscrete MathematicsSeparation AxiomsSpace ComplexityDescriptive Complexity Of PspaceLogarithmic Space ComplexitySeparation Theorems
7
Relationships between nondeterministic and deterministic tape complexities
Walter J. Savitch · Journal of Computer and System Sciences · 1970 · 1.4K citations
Computing, Computer Science, Algorithms +5
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
T. P. Baker, John Gill, Robert M Solovay · SIAM Journal on Computing · 1975 · 738 citations
Computing, Computer Science, Algorithms +10
Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
Stephen Cook · Journal of the ACM · 1971 · 362 citations · Full text
Computing, Computer Science, Computer Architecture +6
Relativization of questions about log space computability
Richard E. Ladner, Nancy Lynch · Theory of Computing Systems · 1976 · 169 citations
Computing, Computer Science, Mathematics +10
Quantitative Relativizations of Complexity Classes
Ronald V. Book, Timothy J. Long, Alan L. Selman · SIAM Journal on Computing · 1984 · 144 citations
Computing, Computer Science, Mathematics +17