<p>One is used to this kind of argument because of what happens in <span class="math-container">$P$</span> and <span class="math-container">$NP$</span>. However, one has to go back to why it is the case in general. If <span class="math-container">$P \in B$</span> is <span class="math-container">$A$</span>-complete <strong>under <span class="math-container">$\prec$</span>-reductions</strong> and <span class="math-container">$B \subseteq A$</span> <strong>and B is closed under <span class="math-container">$\prec$</span>-reduction</strong>, then <span class="math-container">$A = B$</span>. Indeed, if <span class="math-container">$Q \in A$</span>, then <span class="math-container">$Q \prec P$</span> since <span class="math-container">$P$</span> is <span class="math-container">$A$</span>-complete. It follows <span class="math-container">$Q \in B$</span> since <span class="math-container">$P \in B$</span> and <span class="math-container">$B$</span> is closed under <span class="math-container">$\prec$</span>-reductions.</p>
<p>The completeness of <span class="math-container">$DET$</span> for <span class="math-container">$VQP$</span> [1, Theorem 3] is under <span class="math-container">$qp$</span>-projections [1, Definition 9] but <span class="math-container">$VP$</span> is <strong>not</strong> closed under <span class="math-container">$qp$</span>-projection (it seems unlikely and actually has been proven unconditionally in [2, Corollary 8.8] where it is shown that <span class="math-container">$VP \neq VQP$</span>). Hence your argument is not correct and algebraic complexity researcher still have work to do !</p>
<p>Observe that the completeness of <span class="math-container">$DET$</span> for both <span class="math-container">$VQP$</span> and <span class="math-container">$VP_{ws}$</span> comes from the same core argument: one can show that the polynomial computed by an algebraic branching program of size <span class="math-container">$s$</span> can be expressed as the determinent of an <span class="math-container">$s' \times s'$</span> matrix with <span class="math-container">$s'$</span> polynomial in <span class="math-container">$s$</span>. Now, one can simulate any circuit of size <span class="math-container">$t$</span> in <span class="math-container">$VQP$</span> (resp. <span class="math-container">$VP_{ws}$</span>) by an algebraic branching program of size quasi-polynomial (resp. polynomial) hence the completeness of <span class="math-container">$DET$</span>.</p>
<p>As you can see, this works for <span class="math-container">$VQP$</span> under <span class="math-container">$qp$</span>-reduction since the transformed circuit into algebraic branching program is of quasi-polynomial size in the original circuit.</p>
<h1>References</h1>
<p>[1] Malod, G., &amp; Portier, N. (2008). <em>Characterizing Valiant's algebraic complexity classes.</em> Journal of complexity, 24(1), 16-38.</p>
<p>[2] Bürgisser, P. (2000). <em>Completeness and reduction in algebraic complexity theory</em> (Vol. 7). Springer Science &amp; Business Media.</p>

CC BY-SA 4.0
2022-12-12T18:44:37.417Z
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?
Joshua Grochow
CC BY-SA 4.0
2022-12-12T19:53:40.550Z
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
CC BY-SA 4.0
2022-12-12T07:10:56.677Z
2022-12-12T19:56:59.870Z
2022-12-12T19:56:59.870Z
holf
<p>We know that <span class="math-container">$DET$</span> is in <span class="math-container">$VP$</span>. And also from <a href="https://conferences.mpi-inf.mpg.de/adfocs-17/material/MB_LN.pdf" rel="noreferrer">https://conferences.mpi-inf.mpg.de/adfocs-17/material/MB_LN.pdf</a> I came to know that <span class="math-container">$DET$</span> is <span class="math-container">$VQP-complete$</span>. Now certainly <span class="math-container">$VP\subseteq VQP$</span>. That implies <span class="math-container">$VP=VQP$</span>. But there must be something wrong I am deducing but I can't find it. Where I am wrong?</p>

CC BY-SA 4.0
2022-12-11T19:09:18.190Z
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
<complexity-classes><algebraic-complexity>
DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$
Sassy Math
# DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$

(Asked by: username_0 on 2022-12-11)

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?

**Tags:** complexity-classes, algebraic-complexity

> **Comments:**
> **username_1**: 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$.  

---

## 1 answers

### Answer by username_1 on 2022-12-12. Score: 5 | Accepted answer

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.

> **Comments:**
> **username_2**: 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?  
> **username_1**: 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!  

---

