论文标题
实际二次方程的测试系统用于近似解决方案
Testing systems of real quadratic equations for approximate solutions
论文作者
论文摘要
考虑方程式$ q_i（x）= 0 $，其中$ q_i：{\ bbb r}^n \ longrightArrow {\ bbb r} $，$ i = 1，\ ldots，m $是二次形式。我们的目标是从远离使用解决方案的系统中告诉具有许多非平凡解决方案或近溶液$ x \ ne 0 $的有效系统。为此，我们选择了一个三角形的罚款功能$ f：{\ bbb r} \ longrightArrow [0，1] $，$ f（0）= 1 $和$ f（y）<1 $ for $ y \ ne 0 $ 0 $，并计算$ f（q_1（x）（q_1（x））$ cdots f（q_m x）$ sample $ f（x）的期望$ {\ bbb r}^n $。我们选择$ f（y）= y^{ - 2} \ sin^2 y $，并表明期望可以在相对错误$ 0 <ε<ε<1 $ in quasi-polynomial时间$ $ $（m+n）^{o（\ ln（m+n） - \ ln（m+n） - \lnε）} $，提供$ q_i $ novile $ qu_i $ in novers in novers in novers $ qu_i $ qualbles， $ r-1 $其他表格并满足$ | q_i（x）| \leqγ\ | x \ |^2/r $，其中$γ> 0 $是绝对常数。这使我们能够在某些非平凡的情况下区分“易于解决”和“不可解决的”系统。
Consider systems of equations $q_i(x)=0$, where $q_i: {\Bbb R}^n \longrightarrow {\Bbb R}$, $i=1, \ldots, m$, are quadratic forms. Our goal is to tell efficiently systems with many non-trivial solutions or near-solutions $x \ne 0$ from systems that are far from having a solution. For that, we pick a delta-shaped penalty function $F: {\Bbb R} \longrightarrow [0, 1]$ with $F(0)=1$ and $F(y) < 1$ for $y \ne 0$ and compute the expectation of $F(q_1(x)) \cdots F(q_m(x))$ for a random $x$ sampled from the standard Gaussian measure in ${\Bbb R}^n$. We choose $F(y)=y^{-2}\sin^2 y$ and show that the expectation can be approximated within relative error $0< ε< 1$ in quasi-polynomial time $(m+n)^{O(\ln (m+n)-\ln ε)}$, provided each form $q_i$ depends on not more than $r$ real variables, has common variables with at most $r-1$ other forms and satisfies $|q_i(x)| \leq γ\|x\|^2/r$, where $γ>0$ is an absolute constant. This allows us to distinguish between "easily solvable" and "badly unsolvable" systems in some non-trivial situations.
