Tys*_*ams 7 algorithm wolfram-mathematica time-complexity space-complexity
数学" CylindricalDecomposition实现称为圆柱代数分解的算法.Wolfram MathWorld关于圆柱代数分解的文章称,这种算法"在计算上对于复杂的不等式变得不可行".
这句话可以更精确吗？具体来说,时间和空间如何与多元多项式的变量的次数和数量相关？时间和空间是否依赖于其他参数？
Dr.*_*ius 10
Tarski表明,对于包括量子化器在内的每个公式,总会有一个等效的量化器自由公式.从前者获得后者称为量化器消除.(......)
特别地,对于圆柱代数分解(CAD),操作的数量通常以变量的数量以双指数方式缩放,而较新的方法在量化交替的数量中是双指数的.
参考:麻省理工学院6.972代数技术和Pablo A. Parrilo的半有限优化
编辑:这里有一篇关于Mma CAD算法的好文章