Unsatisfiable systems of equations, over a finite field
Unsatisfiable systems of equations, over a finite field
复制标题
有限域上不可满足的方程组
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Alan R. Woods
中科院分区：
文献类型：
--
作者：
Alan R. Woods
本文研究了GF（q）上任意k个n元联立方程组的性质，特别着重于不可满足方程组。给出了解的个数的一般公式，在所有方程都是二次方程的特殊情况下，这个公式实际上可以用来计算解的个数。当这样一个二次系统没有解时，总有一个证明，证明大小q/sup n/2/乘以n和q中的多项式是不可满足的，这可以在满足类似界限的时间上确定性地检查。这样的证明可以找到一个概率算法在时间渐近的测试所需的，通过替代在k二次方程，所有q/supn/潜在的解决方案。
The properties of any system of k simultaneous equations in n variables over GF(q), are studied, with a particular emphasis on unsatisfiable systems. A general formula for the number of solutions is given, which can actually be useful for computing that number in the special case where all the equations are of degree 2. When such a quadratic system has no solution, there is always a proof of unsatisfiability of size q/sup n/2/ times a polynomial in n and q, which can be checked deterministically in time satisfying a similar bound. Such a proof can be found by a probabilistic algorithm in time asymptotic to that required to test, by substitution in k quadratic equations, all q/sup n/ potential solutions.