4
$\begingroup$

We know that languages defined by (poly-sized) Boolean formulae equals $\mathbf{NC}^1$: that Boolean formulae can be simulated in $\mathbf{NC}^1$ was shown by Brent/Spira [B,S], and the converse is quite trivial (simply duplicate the circuit whenever there is a ''collision''). A proof can be found, e.g., in this lecture note by Pitassi (Theorem 3).

Boolean formulae (since the underlying graph is a binary tree) can be thought of as circuits with treewidth $1$, where treewidth of a circuit can be defined as the treewidth of the graph obtained by ignoring the direction of the wires. Gal and Jang [GJ] extended the result in [B,S] by showing that a circuit of size $s$ with treewidth $w$ can be simulated in depth $w\log(s)$. My question is whether the converse is also true: e.g., whether $\mathbf{NC}^2$ can be simulated using circuits with treewidth $\log(s)$ with only a polynomial blow-up (and more generally, whether $\mathbf{NC}^i$ can be simulated using circuits with treewidth $O(\log^{i-1}(s))$).

Intuitively, this should hold (by following the tree decomposition and then using the duplicating trick). But I could not find any resource regarding this (which makes me wonder whether it is false and there is a blow-up in some step). Any pointers would be appreciated!

[B]: Brent, The Parallel Evaluation of General Arithmetic Expressions. Journal of the ACM, 1974.

[GJ]: Gàl and Jang, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Inf. Comput., 2016.

[S]: Spira, On time-hardware complexity tradeoffs for Boolean functions. Hawaii Symp. on System Sciences, 1971.

$\endgroup$
2
  • 1
    $\begingroup$ Did you mean to ask whether $\mathrm{NC}^w$ can be simulated by polynomial-size circuits of tree-width $O((\log n)^{w-1})$? As written, the question does not seem to make much sense: for constant $w$, polynomial-size circuits of tree-width $w$ only recognize $\mathrm{NC}^1$ languages (by the result you quote), hence they cannot recognize $\mathrm{NC}^w$ languages for $w\ge2$ unless the NC hierarchy collapses to $\mathrm{NC}^1$. $\endgroup$ – Emil Jeřábek Feb 28 at 12:23
  • $\begingroup$ Yes, my bad. Have amended the question. $\endgroup$ – Occams_Trimmer Feb 28 at 13:49

Your Answer

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

Browse other questions tagged or ask your own question.