17

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.

Shiva Kintali
  • 10,578
  • 41
  • 74

3 Answers3

10

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.

SamiD
  • 2,309
  • 17
  • 28
  • 1
    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. – Derrick Stolee Jul 19 '11 at 15:16
9

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

Derrick Stolee
  • 2,044
  • 1
  • 21
  • 34
  • 3
    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. – Shiva Kintali Dec 01 '10 at 06:49
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!)

Neel Krishnaswami
  • 32,528
  • 1
  • 100
  • 165
  • 2
    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. – Derrick Stolee Jul 19 '11 at 15:13