<p>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. </p>

CC BY-SA 3.0
2013-10-29T22:18:05.673Z
2013-10-29T22:18:05.673Z
Sebastian Siebertz
<p>The following is not believed to be true:</p>

<blockquote>
  <p>$\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$</p>
</blockquote>

<p>Can you help me see where the argument breaks down?</p>

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

<hr>

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

<p>The directed reachability problem is in $\mathsf{MSO}_2$:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>From Elberfeld, Jakoby, and Tantau's
<a href="http://eccc.hpi-web.de/report/2010/062/" rel="nofollow">Logspace versions of the theorems of Bodlaender and Courcelle</a>:</p>

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

<p>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$.</p>

<p>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$.</p>

<p>(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).</p>

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

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

<p>For us it suffices to observe that from <a href="http://dx.doi.org/10.1006/jcss.1998.1588" rel="nofollow">Nondeterministic $\mathsf{NC^1}$ Computation</a> 
by Caussinus-Mackenzie-Therien-Vollmer:</p>

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

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

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

CC BY-SA 3.0
2013-10-28T05:01:13.873Z
@Kaveh Made the changes you suggested. Thanks.
SamiD
CC BY-SA 3.0
2013-10-28T10:35:06.127Z
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$.
David Richerby
CC BY-SA 3.0
2013-10-28T12:14:59.793Z
@DavidRicherby: I don't understand the counterexample. Can you explain?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-10-28T12:17:51.243Z
Are you referring to this paper instead: http://eccc.hpi-web.de/report/2011/128/
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-10-28T12:20:04.287Z
Is the answer not that the bounded width tree decomposition must be given as part of the input for the result to apply?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-10-28T15:47:31.267Z
@Kristoffer I was referring to the paper I had mentioned I.e. given the pointer representation and not the string representation of the graph. The tree decomposition of a forest is easy to find. in any case the argument is existential we just need the existence of a circuit to prove containment in non-uniform NC1 so no need to invoke Bodlaender's theorem.
SamiD
CC BY-SA 3.0
2013-10-28T15:49:23.650Z
@David we want to consider directed reachability and not undirected hence the predicate is as it is described.
SamiD
CC BY-SA 3.0
2013-10-28T16:46:48.897Z
@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.
David Richerby
CC BY-SA 3.0
2013-10-28T17:03:18.317Z
@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.
SamiD
CC BY-SA 3.0
2013-10-28T21:18:53.667Z
I edited the post to make it more readable. Please check that I haven't introduced any errors. Aside from that I don't think the last steps are clear. You are essentially saying you have a theorem about evaluation of MSO over bounded tree-width structures which is stronger than the original theorem. It seems to me that you are saying that they can be evaluated not just in L but actually in NC1/poly. I think that is the part where your argument should break down.
Kaveh
CC BY-SA 3.0
2013-10-28T21:52:18.293Z
@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.
SamiD
CC BY-SA 3.0
2013-10-29T05:17:48.820Z
You are welcome. I still don't understand the last part and how you move from counting the "proof-trees" of an NC1 circuit to an NC1 circuit. Here is another issue: it seems to me that your path variable is not monadic as its length is not bounded by $O(n)$. I also think the circuit $C$ depends on $\varphi$.
Kaveh
CC BY-SA 3.0
2013-10-29T12:55:30.460Z
@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'$.
SamiD
CC BY-SA 3.0
2013-10-29T12:59:09.130Z
@Kaveh: 2. $\varphi$ is $MSO_2$ and not $MSO_1$ i.e. quantification over sets of edges is allowed. Courcelle's theorem allows for $MSO_2$ formulas (in fact EJT version of Courcelle's theorem allows for arbitrary arity relations in the input structure as long as their Gaifman graph has bounded tree-width (see EJT for details)
SamiD
CC BY-SA 3.0
2013-10-29T13:02:02.063Z
@Kaveh 3: Does the circuit depend on $\phi$ - yes it does - I don't think that is the problem. What keeps me awake at night is whether the circuit depends on the structure itself.
SamiD
<cc.complexity-theory><graph-algorithms><complexity-classes><descriptive-complexity><finite-model-theory>
What is wrong with this $\mathsf{L} \subseteq \mathsf{L}-$uniform $\mathsf{NC}^1$ argument?
SamiD
# What is wrong with this $\mathsf{L} \subseteq \mathsf{L}-$uniform $\mathsf{NC}^1$ argument?

(Asked by: username_0 on 2013-10-28)

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](http://eccc.hpi-web.de/report/2010/062/):

> $\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](http://dx.doi.org/10.1006/jcss.1998.1588)
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$

**Tags:** cc.complexity-theory, graph-algorithms, complexity-classes, descriptive-complexity, finite-model-theory
> **Comments:**
> **username_0**: @Kaveh Made the changes you suggested. Thanks.  
> **username_1**: 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$.  
> **username_2**: @DavidRicherby: I don't understand the counterexample. Can you explain?  
> **username_2**: Are you referring to this paper instead: http://eccc.hpi-web.de/report/2011/128/  
> **username_2**: Is the answer not that the bounded width tree decomposition must be given as part of the input for the result to apply?  
> **username_0**: @Kristoffer I was referring to the paper I had mentioned I.e. given the pointer representation and not the string representation of the graph. The tree decomposition of a forest is easy to find. in any case the argument is existential we just need the existence of a circuit to prove containment in non-uniform NC1 so no need to invoke Bodlaender's theorem.  
> **username_0**: @David we want to consider directed reachability and not undirected hence the predicate is as it is described.  
> **username_1**: @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.  
> **username_0**: @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.  
> **username_3**: I edited the post to make it more readable. Please check that I haven't introduced any errors. Aside from that I don't think the last steps are clear. You are essentially saying you have a theorem about evaluation of MSO over bounded tree-width structures which is stronger than the original theorem. It seems to me that you are saying that they can be evaluated not just in L but actually in NC1/poly. I think that is the part where your argument should break down.  
> **username_0**: @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.  
> **username_3**: You are welcome. I still don't understand the last part and how you move from counting the "proof-trees" of an NC1 circuit to an NC1 circuit. Here is another issue: it seems to me that your path variable is not monadic as its length is not bounded by $O(n)$. I also think the circuit $C$ depends on $\varphi$.  
> **username_0**: @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'$.  
> **username_0**: @Kaveh: 2. $\varphi$ is $MSO_2$ and not $MSO_1$ i.e. quantification over sets of edges is allowed. Courcelle's theorem allows for $MSO_2$ formulas (in fact EJT version of Courcelle's theorem allows for arbitrary arity relations in the input structure as long as their Gaifman graph has bounded tree-width (see EJT for details)  
> **username_0**: @Kaveh 3: Does the circuit depend on $\phi$ - yes it does - I don't think that is the problem. What keeps me awake at night is whether the circuit depends on the structure itself.  

---

## 1 answers

### Answer by username_4 on 2013-10-29. Score: 6 | Accepted answer

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.


---

