论文标题
有效的简单替代半代数集
Efficient simplicial replacement of semi-algebraic sets
论文作者
论文摘要
我们证明，对于任何$ \ ell \ geq 0 $，存在一种算法，将其作为输入的描述，描述了半代数子集$ s \ subset $ s \ subset \ subset \ mathbb {r}^k $，由无量词的一阶公式$ ϕ $ for n of the Reals的语言，以及$Δ $ \ ell $ - 等于$ s $。我们的算法的复杂性由$（sd）^{k^{o（\ ell）}} $界定，其中$ s $是公式$ ϕ $中出现的多项式数量，而$ d $ a限制为$ d $。对于固定的$ \ ell $，此限制在$ k $中单一指数。 In particular, since $\ell$-equivalence implies that the homotopy groups up to dimension $\ell$ of $|Δ|$ are isomorphic to those of $S$, we obtain a reduction (having singly exponential complexity) of the problem of computing the first $\ell$ homotopy groups of $S$ to the combinatorial problem of computing the first $\ell$ homotopy groups of a finite simplicial complex of size由$（sd）^{k^{o（\ ell）}} $界定。
We prove that for any $\ell \geq 0$, there exists an algorithm which takes as input a description of a semi-algebraic subset $S \subset \mathbb{R}^k$ given by a quantifier-free first order formula $ϕ$ in the language of the reals, and produces as output a simplicial complex $Δ$, whose geometric realization, $|Δ|$ is $\ell$-equivalent to $S$. The complexity of our algorithm is bounded by $(sd)^{k^{O(\ell)}}$, where $s$ is the number of polynomials appearing in the formula $ϕ$, and $d$ a bound on their degrees. For fixed $\ell$, this bound is singly exponential in $k$. In particular, since $\ell$-equivalence implies that the homotopy groups up to dimension $\ell$ of $|Δ|$ are isomorphic to those of $S$, we obtain a reduction (having singly exponential complexity) of the problem of computing the first $\ell$ homotopy groups of $S$ to the combinatorial problem of computing the first $\ell$ homotopy groups of a finite simplicial complex of size bounded by $(sd)^{k^{O(\ell)}}$.
