Цилиндрическое алгебраическое разложение
- Цилиндрическая алгебраическая декомпозиция (CAD) является фундаментальным понятием в компьютерной алгебре и реальной алгебраической геометрии.
- CAD представляет разложение Rn на связанные полуалгебраические множества, называемые ячейками, с постоянным знаком каждого многочлена.
- Разложение должно удовлетворять условию, что изображения по проекциям ячеек определяют цилиндрическое разложение Rn-k.
- Понятие CAD было введено Джорджем Э. Коллинзом в 1975 году вместе с алгоритмом для его вычисления.
- Вычислительная сложность алгоритма Коллинза равна двойной экспоненте в n.
- Существуют примеры, для которых минимальное число ячеек является дважды экспоненциальным, показывая, что каждый общий алгоритм CAD имеет двойную экспоненциальную сложность.
- САПР предоставляет эффективную версию устранения квантификатора по сравнению с реальными числами, которая имеет большую вычислительную сложность.
- Поиск путей улучшения алгоритма Коллинза или создание алгоритмов с большей сложностью для подзадач является активной областью исследований.
Полный текст статьи: