__
TR24-021 | 29th January 2024 16:53
__

#### On the closures of monotone algebraic classes and variants of the determinant

**Abstract:**
In this paper we prove the following two results.

* We show that for any $C \in {mVF, mVP, mVNP}$, $C = \overline{C}$. Here, $mVF, mVP$, and $mVNP$ are monotone variants of $VF, VP$, and $VNP$, respectively. For an algebraic complexity class $C$, $\overline{C}$ denotes the closure of $C$. For $mVBP$ a similar result was shown. Here we extend their result by adapting their proof.

* We define polynomial families $\{\mathcal{P}(k)_n\}_{n \geq 0}$, such that $\{\mathcal{P}(0)_n\}_{n \geq 0}$ equals the Determinant polynomial. We show that $\{\mathcal{P}(k)_n\}_{n \geq 0}$ is $VBP$ complete for $k=1$ and becomes $VNP$ complete when $k \geq 2$. In particular, $\{\mathcal{P}(k)_n\}$ is $Det^{\neq k}_n(X)$, a polynomial obtained by summing over all signed cycle covers that avoid length $k$ cycles. We show that $Det^{\neq 1}_n(X)$ is complete for $VBP$ and $Det^{\neq k}_n(X)$ is complete for $VNP$ for all $k \geq 2$ over any field $\mathbb{F}$.