2022/07/21 by Suryajith Chillara, Chillara, Suryajith, Coral Grichener +2 · 1 citation
Computer Science · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2207.10588
openalex publication_date 2022/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We say that two given polynomials f, g ∈ R[X], over a ring R, are equivalent under shifts if there exists a vector a ∈ Rn such that f(X+a) = g(X). Grigoriev and Karpinski (FOCS 1990), Lakshman and Saunders (SICOMP, 1995), and Grigoriev and Lakshman (ISSAC 1995) studied the problem of testing polynomial equivalence of a given polynomial to any t-sparse polynomial, over the rational numbers, and gave exponential time algorithms. In this paper, we provide hardness results for this problem. Formally, for a ring R, let SparseShiftR be the following decision problem. Given a polynomial P(X), is there a vector a such that P(X+a) contains fewer monomials than P(X). We show that SparseShiftR is at least as hard as checking if a given system of polynomial equations over R[x1,…, xn] has a solution (Hilbert's Nullstellensatz). As a consequence of this reduction, we get the following results. 1. SparseShift_ℤ is undecidable. 2. For any ring R (which is not a field) such that HNR is NPR-complete over the Blum-Shub-Smale model of computation, SparseShiftR is also NPR-complete. In particular, SparseShiftℤ is also NPℤ-complete. We also study the gap version of the SparseShiftR and show the following. 1. For every function β: ℕ→ℝ+ such that β∈ o(1), Nβ-gap-SparseShift_ℤ is also undecidable (where N is the input length). 2. For R=\mathbbFp, ℚ, ℝ or ℤq and for every β>1 the β-gap-SparseShiftR problem is NP-hard.