<p>Valiant, Skyum, Berkowitz and Rackoff in <a href="https://epubs.siam.org/doi/10.1137/0212043" rel="nofollow noreferrer">https://epubs.siam.org/doi/10.1137/0212043</a> showed that <span class="math-container">$VP=VNC^2$</span>, namely, that arithmetic circuits can be parallelized.</p>
<blockquote>
<p>What is the central reason such a proof fails in boolean world (implying <span class="math-container">$P\neq NC$</span> should be true)?</p>
</blockquote>

CC BY-SA 4.0
2022-09-28T21:31:32.490Z
In Boolean circuits, you have $x^2=x$, hence, you cannot really use the notion of degree that exists in polynomials over a field. This is crucial in VSBR (to make the circuit homogeneous and to define $f(v;w)$, later called the derivative of $v$ wrt $w$).
holf
CC BY-SA 4.0
2022-09-28T21:32:30.617Z
Thank you for the comment.
Turbo
CC BY-SA 4.0
2022-09-29T06:53:37.163Z
Stated other way, you *can* take a Boolean circuit, reinterpret it as an arithmetic circuit, and try to apply [VSBR]. But the circuit will usually compute a polynomial of exponential degree, hence you will not get anything useful.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><boolean-functions><dc.parallel-comp><arithmetic-circuits>
Boolean vs algebraic circuits difference
Turbo
# Boolean vs algebraic circuits difference

(Asked by: username_0 on 2022-09-28)

Valiant, Skyum, Berkowitz and Rackoff in <https://epubs.siam.org/doi/10.1137/0212043> showed that $VP=VNC^2$, namely, that arithmetic circuits can be parallelized.

> What is the central reason such a proof fails in boolean world (implying $P\neq NC$ should be true)?

**Tags:** cc.complexity-theory, complexity-classes, boolean-functions, dc.parallel-comp, arithmetic-circuits
> **Comments:**
> **username_1**: In Boolean circuits, you have $x^2=x$, hence, you cannot really use the notion of degree that exists in polynomials over a field. This is crucial in VSBR (to make the circuit homogeneous and to define $f(v;w)$, later called the derivative of $v$ wrt $w$).  
> **username_0**: Thank you for the comment.  
> **username_2**: Stated other way, you *can* take a Boolean circuit, reinterpret it as an arithmetic circuit, and try to apply [VSBR]. But the circuit will usually compute a polynomial of exponential degree, hence you will not get anything useful.  

---

## 0 answers

