数学' CylindricalDecomposition实现了一种称为圆柱代数分解的算法。 Wolfram MathWorld 关于 Cylindrical Algebraic Decomposition 的文章表示该算法“对于复杂的不等式在计算上变得不可行。”
这个说法可以更精确吗？具体来说，时间和空间与多元多项式的变量的次数和数量有什么关系？时间和空间是否取决于其他参数？
最佳答案
Tarski showed that for every formula including quantifiers there is always an equivalent quantifier free formula. Obtaining the latter from the former is called quantifier elimination. (...)
In particular, for the cylindrical algebraic decomposition (CAD), the number of operations usually scales in a doubly exponential fashion with the number of variables, while the newer methods are doubly exponential in the number of quantifier alternations.
Reference: MIT 6.972 Algebraic techniques and semidefinite optimization by Pablo A. Parrilo
编辑:一篇关于 Mma CAD 算法的好文章 here
关于algorithm - Mathematica 圆柱分解的计算复杂度是多少，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6406006/