Varieties of Doubly-Exponential Behaviour in Cylindrical Algebraic Decomposition

Research output: Contribution to journalConference articlepeer-review

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 languageEnglish
Pages (from-to)31-40
Number of pages10
JournalCEUR Workshop Proceedings
Volume3273
Publication statusPublished - 20 Aug 2022
Event6th Satisfiability Checking and Symbolic Computation-Square Workshop, SC-Square 2021 - Virtual, Online, USA United States
Duration: 19 Aug 202120 Aug 2021

Keywords

  • Cylindrical Algebraic Decomposition
  • Equational Constraints
  • Quantifier Elimination

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Varieties of Doubly-Exponential Behaviour in Cylindrical Algebraic Decomposition'. Together they form a unique fingerprint.

Cite this