# DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$

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?

• 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$.
– holf
Dec 11, 2022 at 19:09

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.

• 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? Dec 12, 2022 at 18:44
• 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!
– holf
Dec 12, 2022 at 19:53