Concepedia

Random walks, universal traversal sequences, and the complexity of maze problems

Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, Charles Rackoff

1979 · 705 citations · 6 references

DOI

Concepts

References

6

Relationships between nondeterministic and deterministic tape complexities

Walter J. Savitch · Journal of Computer and System Sciences · 1970 · 1.4K citations

, , +5

Computational Complexity of Probabilistic Turing Machines

John Gill · SIAM Journal on Computing · 1977 · 694 citations

, , +17

Space-bounded reducibility among combinatorial problems

Neil D. Jones · Journal of Computer and System Sciences · 1975 · 365 citations

, , +12

Random walks on graphs

F. Göbel, A. A. Jagers · Stochastic Processes and their Applications · 1974 · 251 citations · Full text

, , +12

New problems complete for nondeterministic log space

Neil D. Jones, Y. Edmund Lien, William T. Laaser · Theory of Computing Systems · 1976 · 131 citations

, , +11