Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-021 | 29th January 2024 16:53

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


Authors: Prasad Chaugule, Nutan Limaye
Publication: 4th February 2024 09:42
Downloads: 280


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}$.

ISSN 1433-8092 | Imprint