Efficient logspace algorithms

Question

It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, planar graph isomorphism) run in $O(n^k)$ where $k$ is insanely large.

• I am looking for examples of natural problems that are known to be solvable simultaneously in deterministic logspace and $O(n^k)$ time where $k \leq 10$. There is nothing special about 10. Looking at the currently known logspace algorithms, I think $k \leq 10$ is interesting enough.
• Aleliunas et al. showed that undirected st-connectivity is in $RL$ (randomized logspace). The running time of their algorithm is $O(n^3)$. Are there natural problems that can be solved simultaneously in $RL$ and linear time (or) near linear time i. e., $O(n{\log}^i{n})$ time ?

Edit : To make things more interesting let's look at problems that are at least $NC^1$-hard.

• Hsien-Chih Chang 張顯之: Is there any time analysis to the logspace version of Courcelle's theorem? eccc.uni-trier.de/report/2010/062

Answer 1

I guess Single-source Single-sink Planar DAG (SSPD) reachability has logspace algorithm with a modest running time ($O(n^2)$?). I am not so sure about Single-source Multiple-sink Planar DAG Reachability (SMPD) algorithm.

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009)

Also, a new logspace algorithm for planarity testing and embedding runs in modestly polynomial time (modulo undirected reachability, of course)

Ref: Samir Datta, Gautam Prakriya: Planarity Testing Revisited CoRR abs/1101.2637: (2011)

Finally, here is a simple toy problem which has a logspace algo with a modest running time (modulo undirected reachability) viz. Outerplanar Isomorphism.

• Derrick Stolee: The SSPD algorithm is $O(n^2)$ after the planar embedding is found and uses the fact that there is are linear-time, log-space walkable "left-most" and "right-most" paths from any vertex to the sink or the source to any vertex (call these "outer" paths). For finding a path from $u$ to $v,ドル check if the vertices on the outer paths from u to the sink are along the outer paths from the source to v.

Answer 2

This answer is more of a toy problem than a real research problem.

My typical example of a log-space algorithm to give to programmer friends is the following puzzle:

Given a linked list of unknown size ($n$) and using a constant number of pointer variables, determine if the linked list ever loops.

The solution is a log-space algorithm, using two $O(\log n)$-sized pointers to linked list nodes. Start both at the start of the linked list and perform the following iterative procedure:

• Advance the first pointer in the list by one step.
• Advance the second pointer in the list by two steps.
• If either pointer finds the end, return false.
• If the nodes point to the same node, return true.
• Otherwise, iterate again.

This process will eventually terminate. If there is no loop, it will take $n$ steps. If there is a loop, the two-step pointer cannot pass the one-step pointer without a collision, and this occurs before the one-step pointer finishes the loop (which is under $n$ steps).

• Shiva Kintali: Yes. There are many linked list problems (insertion, deletion, merging) that fall in this category. To make things more interesting let's look at problems that are at least $NC^1$-hard.

Answer 3

The Deutsch-Schorr-Waite algorithm is an $O(n)$ graph marking algorithm, variants of which form the heart of many garbage collector implementations. The problem is to mark the nodes of a graph reachable from a root node. The naive recursive traversal needs linear space to hold the stack of visited nodes, but the DSW algorithm encodes that stack by a cunning link reversal trick -- when it follows an edge, it changes the edge it followed to reverse the source and target, so that it can encode the stack in the graph itself.

IIUC, I think this satisfies your $NC^1$ requirement because additional processors don't help you traverse the graph if if it happens to be organized as a linked list. (This is, in fact, a big PITA for practical garbage collection algorithms!)

• Derrick Stolee: Since you are changing the graph, this is not a log-space algorithm, where the input tape must be read-only. This is an interesting algorithm on its own.