Back to search

Log space machines with multiple oracle tapes

Data up to Jan 2025

Published1978
Citations25
References21

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

Cited By (0)

Loading...