On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

Abstract

We say that two given polynomials $f,g\in R[X]$, over a ring $R$, are equivalent under shifts if there exists a vector $a\in R^n$ 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 ${\mathrm{SparseShift}}_R$ 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 ${\mathrm{SparseShift}}_R$ is at least as hard as checking if a given system of polynomial equations over $R[x_1,\dots ,x_n]$ has a solution (Hilbert's Nullstellensatz). As a consequence of this reduction, we get the following results. 1. ${\mathrm{SparseShift}}_{\mathbb{Z}}$ is undecidable. 2. For any ring $R$ (which is not a field) such that ${\mathrm{HN}}_R$ is ${\mathrm{NP}}_R$-complete over the Blum-Shub-Smale model of computation, ${\mathrm{SparseShift}}_R$ is also ${\mathrm{NP}}_R$-complete. In particular, ${\mathrm{SparseShift}}_{\mathbb{Z}}$ is also ${\mathrm{NP}}_{\mathbb{Z}}$-complete. We also study the gap version of the ${\mathrm{SparseShift}}_R$ and show the following. 1. For every function $\beta :\mathbb{N}\to {\mathbb{R}}_{+}$ such that $\beta \in o(1)$, $N^{\beta }$-gap-${\mathrm{SparseShift}}_{\mathbb{Z}}$ is also undecidable (where $N$ is the input length). 2. For $R={\mathbb{F}}_p,\mathbb{Q},\mathbb{R}$ or ${\mathbb{Z}}_q$ and for every $\beta >1$ the $\beta$-gap-${\mathrm{SparseShift}}_R$ problem is $\mathrm{NP}$-hard.