go-v.orgdoi

Space Lower Bounds for Maze Threadability on Restricted Machines

Stephen A Cook, Charles Rackoff · SIAM Journal on Computing · 1980

  • DOI 10.1137/0209048
  • Publisher Society for Industrial and Applied Mathematics
  • Type article
  • Issued 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)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 06:08 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1137/0209048
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.