Un algoritmo recursivo de proyección y elevación que particiona el espacio real de dimensión n en un número finito de celdas dispuestas cilíndricamente (celdas cuyas proyecciones a dimensiones inferiores son celdas de la descomposición) sobre las cuales un conjunto finito de polinomios reales mantiene signo invariante, permitiendo procedimientos de decisión para consultas de signo y cuantificadores reales.

Principio

Proyectar conjuntos de polinomios variable a variable para calcular polinomios de proyección que capturen condiciones frontera, luego elevar aislando raíces reales y construyendo celdas en dimensiones superiores de modo que cada celda sea signo‑invariante para los polinomios originales; la condición cilíndrica garantiza apilamientos compatibles de celdas entre dimensiones.

Demostración

Para decidir ∃x p(x,y)>0, proyectar p en x para obtener discriminantes y resultantes en y, hallar valores críticos de y que particionan la recta real, y luego por cada intervalo elevar calculando puntos muestreo en x y patrones de signos para determinar si existe x con p>0 en esa celda en y.

Aplicación incorrecta

Emplear CAD indiscriminadamente en problemas con muchas variables o altos grados conduce a cálculos inviables porque la proyección genera muchos polinomios; aplicar CAD a problemas complejos (no reales) o ignorar garantías de aislamiento de raíces numéricas puede producir descripciones de celdas incorrectas.

Consecuencia

CAD proporciona un procedimiento de decisión completo para fórmulas de primer orden sobre cuerpos reales cerrados: genera descomposiciones explícitas de celdas que resuelven cuantificadores y condiciones de signo, y puede proporcionar puntos de muestra y descripciones exactas de conjuntos semialgébricos a costa de elevada complejidad en algunos casos.

Inversión

En lugar de un CAD completo puede usarse CAD parcial, sustitución virtual o muestreo numérico y métodos de intervalos para responder consultas específicas; esto sustituye la descomposición cilíndrica signoinvariante completa por alternativas más baratas pero quizá incompletas.

Límite

Se aplica a polinomios con coeficientes reales y a eliminación de cuantificadores reales; no trata directamente funciones trascendentes ni consultas en variables complejas, y no escala eficientemente a muchas variables y altos grados sin heurísticas o reducciones específicas del problema.

Tensión semántica

CAD garantiza invariancia de signo y decidibilidad para problemas de cuantificadores reales pero sufre una complejidad peor caso doblemente exponencial; métodos como bases de Gröbner o solucionadores numéricos pueden ser más eficientes para tareas algebraicas o aproximadas pero carecen de la generalidad de CAD para cuantificadores reales.

Síntesis

La Descomposición Algebraica Cilíndrica es un esquema de proyección y elevación que produce una partición finita signo‑invariante del espacio real en celdas compatibles cilíndricamente; transforma preguntas de cuantificadores y signo sobre polinomios en comprobaciones combinatorias sobre celdas y puntos de muestra, intercambiando decidibilidad general por alto coste computacional.