On The Closures of Monotone Algebraic Classes and Variants of the Determinant

期刊论文
发表日期：

2024年3月25日

查看全文

Prasad Chaugule,
Nutan Limaye

摘要

In this paper we prove the following two results.

We show that for any $C \in \{\textsf {mVF}, \textsf {mVP}, \textsf {mVNP}\}$ $C \in {mVF, mVP, mVNP}$ , $C = \overline{C}$ $C = \bar{C}$ . Here, $\textsf {mVF}, \textsf {mVP}$ $mVF, mVP$ , and $\textsf {mVNP}$ $mVNP$ are monotone variants of $\textsf {VF}, \textsf {VP}$ $VF, VP$ , and $\textsf {VNP}$ $VNP$ , respectively. For an algebraic complexity class C, $\overline{C}$ $\bar{C}$ denotes the closure of C. For $\textsf {mVBP}$ $mVBP$ a similar result was shown in Bläser et al. (in: 35th Computational Complexity Conference, CCC 2020. LIPIcs, vol 169, pp 21–12124, 2020. https://doi.org/10.4230/LIPIcs.CCC.2020.21). Here we extend their result by adapting their proof.

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