Space Lower Bounds for Maze Threadability on Restricted Machines
Stephen A Cook, Charles Rackoff · SIAM Journal on Computing · 1980
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
SIAM Journal on Computing · Society for Industrial and Applied Mathematics · article · 1980
Abstract
A restricted model of a Turing machine called a JAG (Jumping Automaton for Graphs) is introduced for solving the maze threadability problem (determining whether there is a path joining two distinguished nodes in an input graph). A JAG accesses its input graph by moving pebbles from a limited supply along the edges of the graph under a finite state control, and detecting when two pebbles coincide. It can also cause one pebble to jump to another. We prove that for every N there is a JAG which can determine threadability of an arbitrary N node input graph in storage $O((\log N)^2 )$, where the storage of a JAG with Ppebbles and N states is defined to be $P\log N + \log Q$.
Further, we prove that any JAG which determines threadability requires storage $\Omega ((\log N)^2 /\log \log N)$. Finally, we prove that even when the inputs are restricted to undirected graphs (with no bound on the number of nodes), no single JAG can determine threadability.
Open the resolved locator · 10.1137/0209048
Metadata licence: OpenAlex metadata (CC0)