We present a new algorithm for determining the satisfiability of conjunctions of non-linear polynomial constraints over the reals, which can be used as a theory solver for satisfiability modulo theory (SMT) solving for non-linear real arithmetic. The algorithm is a variant of Cylindrical Algebraic Decomposition (CAD) adapted for satisfiability, where solution candidates (sample points) are constructed incrementally, either until a satisfying sample is found or sufficient samples have been sampled to conclude unsatisfiability. The choice of samples is guided by the input constraints and previous conflicts. The key idea behind our new approach is to start with a partial sample; demonstrate that it cannot be extended to a full sample; and from the reasons for that rule out a larger space around the partial sample, which build up incrementally into a cylindrical algebraic covering of the space. There are similarities with the incremental variant of CAD, the NLSAT method of Jovanović and de Moura, and the NuCAD algorithm of Brown; but we present worked examples and experimental results on a preliminary implementation to demonstrate the differences to these, and the benefits of the new approach.
|Number of pages||41|
|Journal||Journal of Logical and Algebraic Methods in Programming|
|Early online date||27 Nov 2020|
|Publication status||Published - Feb 2021|
Bibliographical noteThis is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
FunderEPSRC Project EP/T015748/1
- Cylindrical algebraic decomposition
- Non-linear real arithmetic
- Real polynomial systems
- Satisfiability modulo theories
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics