solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看249次
Computing the homology of basic semialgebraic sets in weak exponential time. (arXiv:1706.07473v1 [cs.CG])
来源于:arXiv
We describe and analyze an algorithm for computing the homology (Betti
numbers and torsion coefficients) of basic semialgebraic sets which works in
weak exponential time. That is, out 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
which is doubly exponential (and this is so for almost all data). 查看全文>>