Mathematica 的CylindricalDecomposition实现了一种称为圆柱代数分解的算法。Wolfram MathWorld 关于圆柱代数分解的文章称，该算法“对于复杂的不等式在计算上变得不可行”。
这个说法可以更准确吗？具体来说，时间和空间如何与多元多项式的变量的次数和数量相关？时间和空间是否取决于其他参数？
问问题
540 次
1 回答
10
Tarski 表明，对于每一个包括量词的公式，总是有一个等价的无量词公式。从前者获得后者称为量词消除。(...)
特别是对于圆柱代数分解 (CAD)，操作的数量通常随着变量的数量以双指数方式缩放，而较新的方法在量词交替的数量上是双指数的。
参考： Pablo A. Parrilo的 MIT 6.972 代数技术和半定优化
编辑：这里有一篇关于 Mma CAD 算法的好文章
于 2011-06-20T01:10:12.603 回答