En matemáticas , la descomposición algebraica cilíndrica ( CAD ) es una noción, junto con un algoritmo para calcularla, que es fundamental para el álgebra computacional y la geometría algebraica real . Dado un conjunto S de polinomios en R n , una descomposición algebraica cilíndrica es una descomposición de R n en conjuntos semialgebraicos conexos llamados celdas , en los que cada polinomio tiene signo constante, ya sea +, − o 0. Para ser cilíndrica , esta descomposición debe satisfacer la siguiente condición: Si 1 ≤ k < n y π es la proyección de R n sobre R n − k que consiste en eliminar las últimas k coordenadas, entonces para cada par de celdas c y d , se tiene π ( c ) = π ( d ) o π ( c ) ∩ π ( d ) = ∅. Esto implica que las imágenes por π de las celdas definen una descomposición cilíndrica de R n − k .
El concepto fue introducido por George E. Collins en 1975, junto con un algoritmo para calcularlo.
El algoritmo de Collins tiene una complejidad computacional que es doblemente exponencial en n . Este es un límite superior que se alcanza en la mayoría de las entradas. También hay ejemplos en los que el número mínimo de celdas es doblemente exponencial, lo que demuestra que todo algoritmo general para la descomposición algebraica cilíndrica tiene una complejidad doblemente exponencial.
El CAD proporciona una versión eficaz de la eliminación de cuantificadores sobre los números reales que tiene una complejidad computacional mucho mejor que la resultante de la prueba original del teorema de Tarski-Seidenberg . Es lo suficientemente eficiente como para ser implementado en una computadora. Es uno de los algoritmos más importantes de la geometría algebraica real computacional . La búsqueda de mejoras en el algoritmo de Collins, o de proporcionar algoritmos que tengan una mejor complejidad para subproblemas de interés general, es un campo activo de investigación.