The Complexity of Cylindrical Algebraic Decomposition
主 题: The Complexity of Cylindrical Algebraic Decomposition
报告人: Prof. James H. Davenport (University of Bath, UK)
时 间: 2018-04-13 15:00-16:00
地 点: Room 1560, Sciences Building No. 1
Abstract: When Collins [Col75] produced his Cylindrical Algebraic Decomposition algorithm, the complexity was $O\left(d^{2^{2n+8}}m^{2^{n+6}}\right)$, where $n$ is the number of variables, $d$ the maximum degree of any input polynomial in any variable, $m$ the number of polynomials occurring in the input. McCallum [McC84] reduced the double-exponent of $d$ to $n+O(1)$ conditional on the problem being well-oriented. Conversely [DH88, BD07] this is $\Omega(a)$ where $a$ is the number of alternations.
We will describe recent results [ED16, DE16] that reduce the complexity in the presence of equational constraints, and also look at some theoretical limitations.
