Space Lower Bounds for Maze Threadability on Restricted Machines
1980; Society for Industrial and Applied Mathematics; Volume: 9; Issue: 3 Linguagem: Inglês
10.1137/0209048
ISSN1095-7111
AutoresStephen Cook, Charles Rackoff,
Tópico(s)DNA and Biological Computing
ResumoA 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.
Referência(s)