We know that $DET$ is in $VP$. And also from https://conferences.mpi-inf.mpg.de/adfocs-17/material/MB_LN.pdf I came to know that $DET$ is $VQP-complete$. Now certainly $VP\subseteq VQP$. That implies $VP=VQP$. But there must be something wrong I am deducing but I can't find it. Where I am wrong?
$\begingroup$
$\endgroup$
1
-
4$\begingroup$ It is VQP-complete but for different reductions than for VP (for VQP, one is allowed to reduce $f_n$ to $g_{q(n)}$ where $q$ is $n^{O(\log(n))}$). Hence it does not imply $VP = VQP$. $\endgroup$– holfDec 11, 2022 at 19:09
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
One is used to this kind of argument because of what happens in $P$ and $NP$. However, one has to go back to why it is the case in general. If $P \in B$ is $A$-complete under $\prec$-reductions and $B \subseteq A$ and B is closed under $\prec$-reduction, then $A = B$. Indeed, if $Q \in A$, then $Q \prec P$ since $P$ is $A$-complete. It follows $Q \in B$ since $P \in B$ and $B$ is closed under $\prec$-reductions.
The completeness of $DET$ for $VQP$ [1, Theorem 3] is under $qp$-projections [1, Definition 9] but $VP$ is not closed under $qp$-projection (it seems unlikely and actually has been proven unconditionally in [2, Corollary 8.8] where it is shown that $VP \neq VQP$). Hence your argument is not correct and algebraic complexity researcher still have work to do !
Observe that the completeness of $DET$ for both $VQP$ and $VP_{ws}$ comes from the same core argument: one can show that the polynomial computed by an algebraic branching program of size $s$ can be expressed as the determinent of an $s' \times s'$ matrix with $s'$ polynomial in $s$. Now, one can simulate any circuit of size $t$ in $VQP$ (resp. $VP_{ws}$) by an algebraic branching program of size quasi-polynomial (resp. polynomial) hence the completeness of $DET$.
As you can see, this works for $VQP$ under $qp$-reduction since the transformed circuit into algebraic branching program is of quasi-polynomial size in the original circuit.
References
[1] Malod, G., & Portier, N. (2008). Characterizing Valiant's algebraic complexity classes. Journal of complexity, 24(1), 16-38.
[2] Bürgisser, P. (2000). Completeness and reduction in algebraic complexity theory (Vol. 7). Springer Science & Business Media.
-
$\begingroup$ How does closure under qp-projection imply VP=VNP? Isn't VQP equal to the closure of VP under qp-projections, or am I missing something? $\endgroup$ Dec 12, 2022 at 18:44
-
1$\begingroup$ You are right, I wrote that too quickly. Actually, we know that VP is not closed under qp-projection, this is proven in Bürgisser's book. I will edit the answer, thanks for having spotted that! $\endgroup$– holfDec 12, 2022 at 19:53