改进的几何定理机器证明的概率性算法

• 作者: 曾振柄 陈明雁
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 几何定理机器证明 确定性算法 概率性算法 构造性几何 变元次数上界
• 年，卷（期）: 2014,（7）
• 所属期刊栏目: 人工智能
• 页码范围: 2080-2084
• 页数: 5页
• 分类号: TP181
• 字数: 8170字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2014.07.2080

摘要

将几何定理机器证明的研究方法概括为确定性算法与概率性算法两大类,针对已有的确定性算法和概率性算法的证明速率偏低或占用内存过大等问题,提出一种改进的概率性算法.主要是在改进对多项式中独立变元次数的上界估计的算法的基础上,结合Schwartz-Zippel定理和统计学理论,通过随机检验若干实例来证明几何定理,并能控制证明结果不真的概率在给定的小范围内.通过改进的概率性算法,成功在2秒内证明出代数法难以证明的五圆定理.最后的多组对比实验进一步表明,改进的概率性算法具有明显高效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	曾振柄	上海大学数学系	12	45	4.0	6.0