17
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Derrick Stolee Jul 19 '11 at 15:16
9
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Shiva Kintali Dec 1 '10 at 6:49
3
$\begingroup$

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!)

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Derrick Stolee Jul 19 '11 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.