## Abstract

It is almost fifty years since cylindrical algebraic decomposition was introduced: it was far better than previous ideas, but the algorithm was doubly exponential in the number of variables. Various mitigations have been developed over the last forty years. But we have known for over thirty years that cylindrical algebraic decomposition has a worst-case lower bound doubly-exponential in the number of quantifier alternations, which in worst case is proportional to the number of variables. This lower bound can describe the degree of the polynomials, or the number of polynomials, or both. This paper explores the reasons for this, and what further developments, theoretical or practical, might be possible.

Original language | English |
---|---|

Pages (from-to) | 31-40 |

Number of pages | 10 |

Journal | CEUR Workshop Proceedings |

Volume | 3273 |

Publication status | Published - 20 Aug 2022 |

Event | 6th Satisfiability Checking and Symbolic Computation-Square Workshop, SC-Square 2021 - Virtual, Online, USA United States Duration: 19 Aug 2021 → 20 Aug 2021 |

## Keywords

- Cylindrical Algebraic Decomposition
- Equational Constraints
- Quantifier Elimination

## ASJC Scopus subject areas

- Computer Science(all)