Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
Martin Tompa · SIAM Journal on Computing · 1982
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.