Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.12251 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929546056433664 |
|---|---|
| author | Baraskar, Omkar Dewan, Agrim Saha, Chandan Sinha, Pulkit |
| author_facet | Baraskar, Omkar Dewan, Agrim Saha, Chandan Sinha, Pulkit |
| contents | An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse asks to check if there exist $A \in \mathrm{GL}(|\mathbf{x}|, \mathbb{F})$ and $\mathbf{b} \in \mathbb{F}^{|\mathbf{x}|}$ such that $f(A\mathbf{x} + \mathbf{b})$ is $s$-sparse. We show that ETsparse is NP-hard over any field $\mathbb{F}$, if $f$ is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed in [Gupta-Saha-Thankey, SODA'23] and [Baraskar-Dewan-Saha, STACS'24]. The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-$3$ arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest $s_0$ such that a given $s$-sparse polynomial $f$ is in the orbit of some $s_0$-sparse polynomial to within a factor of $s^{\frac{1}{3} - ε}$ is NP-hard for any $ε> 0$; observe that $s$-factor approximation is trivial as the input is $s$-sparse. Finally, we show that for any constant $σ\geq 5$, checking if a polynomial (given in sparse representation) is in the orbit of some support-$σ$ polynomial is NP-hard. Support of a polynomial $f$ is the maximum number of variables present in any monomial of $f$. These results are obtained via direct reductions from the $3$-SAT problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_12251 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials Baraskar, Omkar Dewan, Agrim Saha, Chandan Sinha, Pulkit Computational Complexity An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse asks to check if there exist $A \in \mathrm{GL}(|\mathbf{x}|, \mathbb{F})$ and $\mathbf{b} \in \mathbb{F}^{|\mathbf{x}|}$ such that $f(A\mathbf{x} + \mathbf{b})$ is $s$-sparse. We show that ETsparse is NP-hard over any field $\mathbb{F}$, if $f$ is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed in [Gupta-Saha-Thankey, SODA'23] and [Baraskar-Dewan-Saha, STACS'24]. The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-$3$ arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest $s_0$ such that a given $s$-sparse polynomial $f$ is in the orbit of some $s_0$-sparse polynomial to within a factor of $s^{\frac{1}{3} - ε}$ is NP-hard for any $ε> 0$; observe that $s$-factor approximation is trivial as the input is $s$-sparse. Finally, we show that for any constant $σ\geq 5$, checking if a polynomial (given in sparse representation) is in the orbit of some support-$σ$ polynomial is NP-hard. Support of a polynomial $f$ is the maximum number of variables present in any monomial of $f$. These results are obtained via direct reductions from the $3$-SAT problem. |
| title | NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2410.12251 |