5
$\begingroup$

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?

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

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • $\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$
    – holf
    Dec 12, 2022 at 19:53

Your Answer

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

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