SIAM Journal on Computing · 1982 · 23 citations · 14 references
ComputingComputer ScienceMathematicsAlgorithmsDiscrete MathematicsTheory Of ComputationAlgorithm AnalysisBoolean AlgebraComputational ComplexityMatrix ComputationSorting AlgorithmsSpace ComplexityBoolean FunctionsBoolean Matrix AlgebraPolynomial Time ComplexityPolynomial-time AlgorithmsSpace ReductionsSpace-smallnessSublinear Space AlgorithmsTransitive Closure
Any Boolean straight-line program which computes the transitive closure of an $n \times n$ Boolean matrix by successive squaring requires time exceeding any polynomial in n if the space used is $o(n)$. This is the first demonstration of a “natural” algorithm which (1) has a polynomial time implementation and (2) has a small (e.g., $O(\log ^2 n)$) space implementation, but (3) has no implementation running in polynomial time and small space simultaneously. It is also shown that any implementation of Warshall’s transitive closure algorithm requires $\Omega (n)$ space, and that many familiar sorting algorithms exhibit similar behavior.
14
Stephen Warshall · Journal of the ACM · 1962 · 1.7K citations
Random walks, universal traversal sequences, and the complexity of maze problems
Romas Aleliunas, Richard M. Karp, Richard J. Lipton et al. · 1979 · 705 citations
Two theorems on random polynomial time
Leonard M. Adleman · 1978 · 317 citations