<p>The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true as permanent is complete for both VNP and #P. Indeed, the Boolean part of VNP is essentially just #P/poly (it contains #P/poly and is contained in $\mathsf{FP}^{\mathsf{\# P}}/poly$ [Burgisser].</p>

<p>Valiant already observed that $\mathsf{P/poly} \neq \mathsf{NP/poly}$ implies $\mathsf{VP} \neq \mathsf{VNP}$ over $\mathbb{F}_2$, so separating VP from VNP is necessary on the way to proving that NP is not in P/poly. Not only is it a formally necessary first step, but because of the connection between VNP and counting solutions to NP problems, one could imagine that a better understanding of VNP would yield some insight into NP as well.</p>

CC BY-SA 3.0
2015-05-01T23:33:07.873Z
converse to $P/poly\neq NP/poly\implies VP\neq VNP$ likely false right?
Turbo
CC BY-SA 3.0
2015-05-04T23:35:45.943Z
@Turbo: (It's probably not formally false, because we believe that both the antecedent and the consequent are true.) As to whether there is a "direct" implication from $\mathsf{VP} \neq \mathsf{VNP}$ to $\mathsf{P/poly} \neq \mathsf{NP/poly}$: this is not known, but I would say it's also not particularly clear one way or the other. Note that even in the Boolean world we don't know whether $\mathsf{\# P} \neq \mathsf{FP} \Rightarrow \mathsf{P} \neq \mathsf{NP}$.
Joshua Grochow
CC BY-SA 3.0
2015-05-01T20:45:09.980Z
2015-05-01T20:45:09.980Z
Joshua Grochow
<p>Valiant introduced the class <a href="http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Algebraic_P_and_NP" rel="nofollow">VNP</a> with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as cited by <a href="http://blog.computationalcomplexity.org/2014/06/ccc-2014.html" rel="nofollow">Fortnow</a>.</p>

<blockquote>
  <p>What is the intuition that VNP and NP are similar/ analogous in some way? Is there analysis/ results since its introduction that point toward or away from this analogy? Has/ can the study of VNP lead to some insights on NP?</p>
</blockquote>

CC BY-SA 3.0
2015-05-01T20:14:25.177Z
other ideas/ related question: is there any proven equivalent formulation of the P vs NP problem in the arithmetic circuits framework...? or how about, any NP complete problems related to arithmetic circuits?
vzn
CC BY-SA 3.0
2015-05-03T09:55:52.147Z
@Downvoters Please be constructive and leave comments to improve the question. The question is research level and Grochow's answer is very informative.
Mohammad Al-Turkistany
<cc.complexity-theory><reference-request><big-picture><p-vs-np><arithmetic-circuits>
Analogies between VNP and NP
vzn
# Analogies between VNP and NP

(Asked by: username_0 on 2015-05-01)

Valiant introduced the class [VNP](http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Algebraic_P_and_NP) with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as cited by [Fortnow](http://blog.computationalcomplexity.org/2014/06/ccc-2014.html).

> What is the intuition that VNP and NP are similar/ analogous in some way? Is there analysis/ results since its introduction that point toward or away from this analogy? Has/ can the study of VNP lead to some insights on NP?

**Tags:** cc.complexity-theory, reference-request, big-picture, p-vs-np, arithmetic-circuits

> **Comments:**
> **username_0**: other ideas/ related question: is there any proven equivalent formulation of the P vs NP problem in the arithmetic circuits framework...? or how about, any NP complete problems related to arithmetic circuits?  
> **username_1**: @Downvoters Please be constructive and leave comments to improve the question. The question is research level and Grochow's answer is very informative.  

---

## 1 answers

### Answer by username_2 on 2015-05-01. Score: 15 | Accepted answer

The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true as permanent is complete for both VNP and #P. Indeed, the Boolean part of VNP is essentially just #P/poly (it contains #P/poly and is contained in $\mathsf{FP}^{\mathsf{\# P}}/poly$ [Burgisser].

Valiant already observed that $\mathsf{P/poly} \neq \mathsf{NP/poly}$ implies $\mathsf{VP} \neq \mathsf{VNP}$ over $\mathbb{F}\_2$, so separating VP from VNP is necessary on the way to proving that NP is not in P/poly. Not only is it a formally necessary first step, but because of the connection between VNP and counting solutions to NP problems, one could imagine that a better understanding of VNP would yield some insight into NP as well.

> **Comments:**
> **username_3**: converse to $P/poly\neq NP/poly\implies VP\neq VNP$ likely false right?  
> **username_2**: @username_3: (It's probably not formally false, because we believe that both the antecedent and the consequent are true.) As to whether there is a "direct" implication from $\mathsf{VP} \neq \mathsf{VNP}$ to $\mathsf{P/poly} \neq \mathsf{NP/poly}$: this is not known, but I would say it's also not particularly clear one way or the other. Note that even in the Boolean world we don't know whether $\mathsf{\# P} \neq \mathsf{FP} \Rightarrow \mathsf{P} \neq \mathsf{NP}$.  

---

