Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time
Computing the Homology of Basic Semialgebraic Sets in Weak Exponential Time
复制标题
计算弱指数时间内基本半代数集的同调
DOI：
10.1145/3275242
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
P. Lairez
中科院分区：
文献类型：
--
作者：
P. Bürgisser;F. Cucker;P. Lairez
描述并分析了一种计算基本半代数集的同调(Betti数和扭转系数)的算法，该算法工作在弱指数时间。也就是说，对于数据空间中的一组指数小的度量，算法的代价与数据的大小成指数关系。以前为这个问题提出的所有算法的复杂性都是双指数的(几乎所有数据都是如此)。
We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of basic semialgebraic sets that works in weak exponential time. That is, of a set of exponentially small measure in the space of data, the cost of the algorithm is exponential in the size of the data. All algorithms previously proposed for this problem have a complexity that is doubly exponential (and this is so for almost all data).
登录
查看更多内容
DOI：
10.1007/978-3-642-38896-5
发表时间：
2013-08
期刊：
--
影响因子：
--
作者：
Peter Bürgisser;F. Cucker
通讯作者：
Peter Bürgisser;F. Cucker
刚性连续路径 I. 求解多项式系统的拟线性平均复杂度
DOI：
10.1090/jams/938
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Pierre Lairez
通讯作者：
Pierre Lairez
计算半代数集的第一个贝蒂数
影响因子：
3
作者：
S. Basu;R. Pollack;Marie
通讯作者：
Marie
DOI：
10.1145/1060590.1060636
发表时间：
2005-05
期刊：
--
影响因子：
--
作者：
S. Basu;R. Pollack;Marie-Françoise Roy
通讯作者：
S. Basu;R. Pollack;Marie-Françoise Roy
没有黑天鹅的平均情况复杂性
影响因子：
1.7
作者：
Dennis Amelunxen;Martin Lotz
通讯作者：
Martin Lotz