Probabilistic algorithms for verification of polynomial identities (invited)
Probabilistic algorithms for verification of polynomial identities (invited)
复制标题
验证多项式恒等式的概率算法（特邀）
DOI：
--
复制
发表时间：
1979
期刊：
影响因子：
--
通讯作者：
J. Schwartz
中科院分区：
文献类型：
--
作者：
J. Schwartz
Rabin-Strassen-Solovay素性算法的惊人成功，再加上一种耐人寻味的基本可能性，即随机性公理可能构成独立于数学标准公理结构的有用的数学真理的基本来源，这表明人们对概率算法的积极探索。为了说明这一点，我们提出了各种快速概率算法，用于测试多项式恒等式和多项式系统的性质，并保证了先验的正确概率。给出了计算结式和Sturm序列的辅助快速算法。与任何已知的人工智能方法相比，所提供的技术可以更有效地证明初等几何定理。
The startling success of the Rabin-Strassen-Solovay primality algorithm, togehter with the intriguing foundational possibility that axioms of randomness may constitute a useful fundamental source of mathematical truth independent of the standard axiomatic structure of mathematics, suggests a vigorous search for probabilistic algorithms. In illustration of this observation, we present various fast probabilistic algorithms, with probability of correctness guaranteed a priori, for testing polynomial identities and properties of systems of polynomials. Ancillary fast algorithms for calculating resultants and Sturm sequences are given. Theorems of elementary geometry can be proved much more efficiently by the techniques presented than by any known artificial intelligence approach.