Log space machines with multiple oracle tapes
Data up to Jan 2025
Total Citations Per Year
Abstract
References (21)
Reducibility among Combinatorial Problems
1972 • 10,743 citations
The complexity of theorem-proving procedures
1971 • 6,155 citations
Theory of Recursive Functions and Effective Computability.
1969 • 2,849 citations
Theory of Recursive Functions and Effective Computability
1969 • 2,654 citations
Relationships between nondeterministic and deterministic tape complexities
1970 • 1,361 citations
Word problems requiring exponential time(Preliminary Report)
1973 • 865 citations
On the Structure of Polynomial Time Reducibility
1975 • 801 citations
Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
1975 • 750 citations
The equivalence problem for regular expressions with squaring requires exponential space
1972 • 620 citations
A comparison of polynomial time reducibilities
1975 • 430 citations
Relativization of questions about log space computability
1976 • 171 citations
A second step toward the polynomial hierarchy
1979 • 88 citations
On time versus space and related problems
1975 • 81 citations
Tape bounds for time-bounded turing machines
1972 • 48 citations
Complete problems for deterministic polynomial time
1974 • 42 citations
On some subrecursive reducibilities
1977 • 40 citations
Relativization of the theory of computational complexity
1976 • 32 citations
Polynomial reducibilities and upward diagonalizations
1977 • 27 citations
The extension of machine-independent computational complexity theory to oracle machine computation and to the computation of finite-functions.
1972 • 16 citations
A second step toward the polynomial hierarchy
1976 • 13 citations
Deleted Work
1955 • 0 citations