4
$\begingroup$

Valiant introduced the class VNP 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.

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – vzn
    May 1, 2015 at 20:14
  • 1
    $\begingroup$ @Downvoters Please be constructive and leave comments to improve the question. The question is research level and Grochow's answer is very informative. $\endgroup$
    – Mohammad Al-Turkistany
    May 3, 2015 at 9:55

1 Answer 1

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ converse to $P/poly\neq NP/poly\implies VP\neq VNP$ likely false right? $\endgroup$
    – Turbo
    May 1, 2015 at 23:33
  • 2
    $\begingroup$ @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}$. $\endgroup$
    – Joshua Grochow
    May 4, 2015 at 23:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.