2026-08-13T03:10:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20159 2024-07-02T07:52:48Z ddc:004 open_access

NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials Baraskar, Omkar Dewan, Agrim Saha, Chandan Sinha, Pulkit Equivalence testing MCSP sparse polynomials 3SAT 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 ∈ 𝔽[𝐱] and s ∈ ℕ, ETsparse asks to check if there exist A ∈ GL(|𝐱|, 𝔽) and 𝐛 ∈ 𝔽^|𝐱| such that f(A𝐱 + 𝐛) is s-sparse. We show that ETsparse is NP-hard over any field 𝔽, if f is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). 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₀ such that a given s-sparse polynomial f is in the orbit of some s₀-sparse polynomial to within a factor of s^{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 σ ≥ 6, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Omkar Baraskar and Agrim Dewan and Chandan Saha and Pulkit Sinha 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.16 urn:nbn:de:0030-drops-201598 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.16 eng https://creativecommons.org/licenses/by/4.0/legalcode