3
$\begingroup$

We do not know if $P=NP$ has an impact on $VP=VNP$ however how about $P=PP$?

  1. Is $PP$ and $VNP$ related and would $P=PP$ or $P=PSPACE$ imply $VP=VNP$?

  2. Is there a way to show $\#P$ is in $FP^{PP}$?

$\endgroup$
1
$\begingroup$

Note that $\#P\in FP^{PP}$ follows from a simple binary search. Given some non-deterministic machine $M$, the language $\{(x,k) |\#M(x)\ge k\}$, where $\#M(x)$ is the number of accepting paths on input $x$, is in PP (you can change the constant in the definition of PP to any FP function). Thus, using a PP oracle we can count the number of accepting paths via binary search.

This implies that $\mathsf{P=PP}$ puts permanent in $VP$, as the problem of counting the number of perfect matchings in a bipartite graph (or equivalently, computing the permanent of the adjacency matrix) is in $\#P$.

$\endgroup$

Your Answer

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

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