论文标题
关于在偏移下与稀疏多项式的测试硬度的硬度
On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts
论文作者
论文摘要
我们说，如果存在一个$ f（x+a）= g（x）$，则两个给定的polyenmials $ f，g \ in r [x] $在r [x] $中等同于换档。 Grigoriev和Karpinski（Focs 1990），Lakshman和Saunders（Sicomp，1995年）以及Grigoriev和Lakshman（Issac 1995）研究了测试给定多项式对等于$ t $ t $ t $ pary-sparse pare-sparse pare-sparse pare party-sparse partery bick yexparse partymial bict yceptional the Policationality afformational and explimential algorite algorith的问题。在本文中，我们为此问题提供硬度结果。正式地，对于环$ r $，令$ \ mathrm {sparseshift} _r $为以下决策问题。给定一个多项式$ p（x）$，是否有一个vector $ a $，以便$ p（x+a）$包含少于$ p（x）$的单元。我们表明，$ \ mathrm {sparseshift} _r $至少与检查给定的多项式方程式是否在$ r [x_1，\ ldots，x_n] $具有解决方案（Hilbert's nullstellensatz）上一样困难。 由于这种减少，我们得到以下结果。 1。$ \ mathrm {sparseshift} _ \ mathbb {z} $是不可决定的。 2。对于任何环$ r $（这不是字段），以至于$ \ mathrm {hn} _r $是$ \ mathrm {np} _r $ -complete在blum-smale的计算模型上，$ \ mathrm {sparseshift} _ {r} $ - n是$ \ n $ - n是$ \ n $ - 特别是，$ \ mathrm {sparseshift} _ {\ mathbb {z}} $也是$ \ mathrm {np} _ {\ mathbb {z}}} $ - 完成。 我们还研究$ \ mathrm {sparseshift} _r $的差距版本并显示以下内容。 1。对于每个功能，$β：\ mathbb {n} \ to \ mathbb {r} _+$，使得$β\ in O（1）$，$ n^β$ -gap -gap- $ \ $ \ sparseShift} _ \ m mathbb {z} $也是$ n $ nesput（input）。 2。对于$ r = \ mathbb {f} _p，\ mathbb {q}，\ mathbb {r} $或$ \ mathbb {z} _q $，以及每一个$β> 1 $ $β$ -gap -gap -gap -gap- $ \ $ \ m mathrm {sparseShift} $ $ $ \ nprm
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 $β: \mathbb{N}\to\mathbb{R}_+$ such that $β\in o(1)$, $N^β$-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 $β>1$ the $β$-gap-$\mathrm{SparseShift}_R$ problem is $\mathrm{NP}$-hard.
