Does reachability fit in with P? – Information Technology Stack Exchange

Reachability is understood to be follows: a digraph $G = (V, E)$ and 2 vertices $v,w in V$. What is the directed path from $v$ to $w$ in $G$?

Can you really write a polynomial time formula for this?

I requested this on mathematics and also got no answer undoubtedly.

3 Solutions

Although you know in the other solutions that now you ask , solvable in polynomial time, I figured I’d expand around the computational complexity of reachability because you used complexity terminology inside your question.

Reachability (or st-connectivity) in digraphs may be the prototypical $NL$-complete problem where $NL$ means non-deterministic log space so we use deterministic log-space reductions (although It remains complete for $NC^1$ reductions, too).

• To determine why it’s in $NL$, notice that you could guess a next vertex at each step and verify that it’s attached to the previous vertex. A number of correct guesses exists if and just if there’s a way from $s$ to $t$.
• To determine exactly why is $NL$-hard, observe that the behaviour of the non-deterministic Turing machine could be symbolized with a configuration graph. The nondeterministic machine accepts only when there’s a path from the beginning configuration for an accept configuration, and when the device just uses $S(n)$ tape records then your configuration graph is of size $O(Gamma^)$ where $Gamma$ may be the tape alphabet. If $S(n)$ is logarithmic, then your resulting graph is of polynomial size and also the result follows.

But I haven’t got use of a non-deterministic machine, why must i care? Well, we all know many things about $NL$ certainly one of individuals is the fact that is within $P$, that you simply know in the other solutions. However, listed here are tighter details that may be helpful:

• From Savitch’s theorem we all know that $NL subseteq text((log n)^2)$: even on the deterministic machine you do not need much space to resolve the issue.

• We all know that $NL subseteq NC^2$: which means that within the circuit model, your question could be solved with a polynomial sized circuit of depth $O((log n)^2)$. Inside a more “heuristic” sense, which means that the issue is parallelizable since Nick’s Class captures the thought of quick solutions on the parallel computer.

• We all know that $NL subseteq text$ meaning it’s not harder (as much as log-space reductions) than membership checking in context-free languages which may be an excellent source of intuition.

Finally, the directed nature from the graph is important. When the graph is undirected only then do we believe now you ask , considerably simpler. Particularly, undirected st-connectivity is finished for $L$ (deterministic log space) under first-order reductions (Reingold 2004 ).

Yes, this issue is solveable in straight line time, $O(V+E)$ more specifically.

The 2 classic methods to this are Breadth-First search and Depth-First search.

The algorithms essentially seem like this:

current = v
while (current comes with an edge for an unmarked vertex)
    if current == w
        return true
    mark current as visited
    for every u where (v,u) is within E
        add u towards the Open List
    current = a vertex in the Open List
return false

BFS utilizes a queue because the open list, contributing to the rear and taking in the front. DFS utilizes a stack. In almost any implementation such as this, each node and every edge are visited for the most part once, therefore the formula runs in straight line time.

Yes, it’s in P.

Natural formula for really is easy, so simple it does not really function as a chance to learn to condition it here (it’s easily available in any text or on the internet).