Deciding Univariate Polynomial Problems Using Untrusted Certificates in Isabelle/HOL
Published version
Repository URI
Repository DOI
Change log
Authors
Li, W
Passmore, G
Paulson, LC
Abstract
We present a proof procedure for univariate real polynomial problems in Isabelle/HOL. The core mathematics of our procedure is based on univariate cylindrical algebraic decomposition. We follow the approach of untrusted certificates, separating solving from verifying: efficient external tools perform expensive real algebraic computations, producing evidence that is formally checked within Isabelle’s logic. This allows us to exploit highly-tuned computer algebra systems like Mathematica to guide our procedure without impacting the correctness of its results. We present experiments demonstrating the efficacy of this approach, in many cases yielding orders of magnitude improvements over previous methods.
Description
Keywords
interactive theorem proving, Isabelle/HOL, decision procedure, cylindrical algebraic decomposition
Journal Title
Journal of Automated Reasoning
Conference Name
Journal ISSN
0168-7433
1573-0670
1573-0670
Volume Title
Publisher
Springer
Publisher DOI
Sponsorship
The first author was funded by the China Scholarship Council, via the CSC Cambridge Scholarship programme. The development of MetiTarski was supported by the Engineering and Physical Sciences Research Council [Grant Numbers EP/I011005/1, EP/I010335/1].