Что такое вычислительная сложность цилиндрической декомпозиции Mathematica

Question

Mathematica ' Цилиндрическая декомпозиция реализует алгоритм, известный как цилиндрическая алгебраическая декомпозиция.В статье Wolfram MathWorld о цилиндрическом алгебраическом разложении говорится, что этот алгоритм «становится невозможным в вычислительном отношении для сложных неравенств».В частности, как время и пространство связаны со степенью и числом переменных многомерных полиномов?Зависит ли время и пространство от других параметров?

Answer 1

Тарский показал, что для каждой формулы, включая кванторы, всегда есть эквивалентная формула без квантификатора. Получение последнего из первого называется квантификационным устранением. (...)

В частности, для цилиндрической алгебраической декомпозиции (САПР) число операций обычно масштабируется в два раза экспоненциально с числом переменных, в то время как более новые методы имеют вдвое экспоненциальное число чередований квантовых чисел.

Ссылка: MIT 6.972 Алгебраические методы и полуконечная оптимизация Пабло А. Паррило

Редактировать : Хорошая статья об алгоритмах Mma CAD здесь