有序实数加法理论新的判定过程与多项式谱

摘要：

推广Volker Weispfenning关于正的有序实数加法理论的量词消去方法,得到有序实数加法理论的一个量词消去的判定过程.在此基础上构造出一个新的、更为精细的判定方法.并且利用这一结果证明了固定量词长度的子类属于相应计算复杂性的多项式谱.与E.D.Sontag的类似结论比较,从这种简洁的方式可以得到一个较优的结果.这个结果实际上将N.Megiddo的关于正实数理论的结论推广到了一般实数理论.

关键词：实数加法、判定过程、量词的界、量词消去、计算复杂性、多项式谱

所属期刊栏目：12

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金69833020;山西省留学回国人员科研项目97093

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：1088-1093