ECCC-Report TR08-090https://eccc.weizmann.ac.il/report/2008/090Comments and Revisions published for TR08-090en-usWed, 01 Oct 2008 00:00:00 +0300
Revision 1
| Pointer Programs and Undirected Reachability |
Ulrich Schöpp,
Martin Hofmann
https://eccc.weizmann.ac.il/report/2008/090#revision1We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs capture the common description of LOGSPACE algorithms as programs that take as input some structured data (e.g. a graph) and that store in memory only a constant number of pointers to the input (e.g. to the graph nodes). Starting from pure pointer programs, in which only abstract pointers without any internal structure are allowed, we consider pointer programs with constructs for iterating over the input structure and for counting. We classify with which of these constructs it is possible to write a program for solving s-t-reachability in undirected graphs. The main result of this paper is a new lower bound on undirected s-t-reachability. We show that while pointer programs with counting can decide this problem using Reingold's algorithm, the problem cannot be decided by pointer programs with iteration. As a corollary we obtain that Deterministic Transitive Closure logic on locally ordered graphs cannot express undirected s-t-reachability.
Wed, 01 Oct 2008 00:00:00 +0300https://eccc.weizmann.ac.il/report/2008/090#revision1
Paper TR08-090
| Pointer Programs and Undirected Reachability |
Ulrich Schöpp,
Martin Hofmann
https://eccc.weizmann.ac.il/report/2008/090We study pointer programs as a model of structured computation within LOGSPACE. Pointer programs capture the common description of LOGSPACE algorithms as programs that take as input some structured data (e.g. a graph) and that store in memory only a constant number of pointers to the input (e.g. to the graph nodes). Starting from pure pointer programs, in which only abstract pointers without any internal structure are allowed, we consider pointer programs with constructs for iterating over the input structure and for counting. We classify with which of these constructs it is possible to write a program for solving s-t-reachability in undirected graphs.
The main result of this paper is a new lower bound on undirected s-t-reachability. We show that while pointer programs with counting can decide this problem using Reingold's algorithm, the problem cannot be decided by pointer programs with iteration. As a corollary we obtain that Deterministic Transitive Closure logic on locally ordered graphs cannot express undirected s-t-reachability.
Tue, 30 Sep 2008 22:03:21 +0300https://eccc.weizmann.ac.il/report/2008/090