9
$\begingroup$

The following is not believed to be true:

$\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$

Can you help me see where the argument breaks down?

The directed reachability problem is complete for $\mathsf{L}$. I argue that it is in $\mathsf{L}$-uniform $\mathsf{NC^1}$.

The directed reachability problem over configuration graphs of deterministic log-space Turing Machine is complete for $\mathsf{L}$.

The directed reachability problem is in $\mathsf{MSO}_2$:

given $s$ and $t$, let $P$ represent the free $\mathsf{MSO}$ variable for the edges in the path. We need to verify that $P$ contains a directed path from $s$ to $t$ which can be done by verifying that the in-degree and out-degree (in $P$) of every vertex incident on an edge in $P$ is $1$ except for $s$ and $t$ which have in-degree,out-degree = $0,1$ and $1,0$ respectively.

Every forest is a graph of tree-width $1$. In particular the configuration graph of a deterministic log-space Turing Machine is a bounded tree-width structure.

From Elberfeld, Jakoby, and Tantau's Logspace versions of the theorems of Bodlaender and Courcelle:

$\mathsf{MSO}$ formula over bounded tree-width structures can be evaluated in log-space.

The proof goes something like this: For a given structure size $n$, a bound on the tree-width of the structures $w$, and a $\mathsf{MSO}$ formula $\varphi$ with vocabulary $\tau$, construct (in $\mathsf{L}$) construct a $\#\mathsf{NC}^1$ circuit $C$.

The circuit $C$ given a structure $M$ of size $n$ and tree-width at most $w$, counts the number of "satisfying" assignments of $\varphi$ on $M$.

(The histogram tabulating the number of assignments to the free second order variables in $\varphi$ parameterized on the sizes of the sets of values taken by the the variables).

I think the circuit $C$ only depends on the vocabulary $\tau$, the tree-width bound $d$, and the size of structure $n$.

The proof proceeds by evaluating the circuit in $\#\mathsf{NC}^1 \subseteq \mathsf{L}$ but we don't need that part.

For us it suffices to observe that from Nondeterministic $\mathsf{NC^1}$ Computation by Caussinus-Mackenzie-Therien-Vollmer:

every $\#\mathsf{NC}^1$-circuit can be interpreted as counting the number of proof-trees of a $\mathsf{NC}^1$-circuit.

Thus the corresponding circuit outputs $1$ iff the input structure satisfies the $\mathsf{MSO}$ formula.

From the above it seems that log-space is at least in logspace-uniform $\mathsf{NC}^1$

Improve this question
$\endgroup$
15
  • 3
    $\begingroup$ Your MSO reachability argument isn't quite right: it will only work if the subgraph induced by the vertices $P$ is a directed path, which isn't the case in general (a trivial counterexample is a symmetric pair of directed edges). The correct way to do reachability in MSO is to assert that every vertex set that contains $s$ and is closed under the edge relation also includes $t$. $\endgroup$
    – David Richerby
    Commented Oct 28, 2013 at 10:35
  • 2
    $\begingroup$ @SamiD I gave the smallest counter-example, which happens to be a symmetric graph. But the 3-vertex graph with directed edges $a\to b$, $b\to c$, $c\to a$ works just as well: the unique directed path from $a$ to $c$ is $abc$ but the set $\{a,b,c\}$ does not satisfy your formula because, in the subgraph induced by $\{a,b,c\}$ (which is the whole graph), $a$ does not have in-degree zero and $c$ does not have out-degree zero. $\endgroup$
    – David Richerby
    Commented Oct 28, 2013 at 16:46
  • 2
    $\begingroup$ @David Point well-made - my original formulation was buggy - I hope this one is ok: I consider a set of edges instead of vertices and look at the degree of vertices wrt to these edges - they must be same as before. Thanks for the example. $\endgroup$
    – SamiD
    Commented Oct 28, 2013 at 17:03
  • 2
    $\begingroup$ @Kaveh Thanks for the changes - they do make the question more readable. I clarified the issue you raised - in my understanding EJT create a log-depth arithmetic circuit in L and then the problem falls in L because of the CMTV containment #NC1 \subseteq L. But we stop at the point the circuit is created and syntactically convert it to a NC^1 circuit. The conversion etc can be done easily. I converted NC^1/poly to L-uniform NC^1 also because it is more accurate. $\endgroup$
    – SamiD
    Commented Oct 28, 2013 at 21:52
  • 2
    $\begingroup$ @Kaveh: 1. Changing every $+$ of $\#NC^1$-circuit $C$ to $\vee$ and $*$ to $\wedge$ will create an $NC^1$ circuit $C'$ such that $C$ counts the number of proof trees of $C'$. $\endgroup$
    – SamiD
    Commented Oct 29, 2013 at 12:55

1 Answer 1

Reset to default
6
$\begingroup$

In fact, the circuit depends on the input structure, not only on the input structure size. We take a tree-decomposition of the graph with additional colours and turn it into a convolution tree. The evaluation of the formula on this tree is reduced to computing the value of the convolution tree. To compute the value of the tree, it is turned into an arithmetic circuit. Hence we do not get one circuit for each input size as required for $NC^1$, but rather one circuit for each single input.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.