  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,\ldots, 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.
