Homotopy, Complexity and O-Minimality

Andrei Gabrielov建议研究实闭域的o-极小展开中可定义集的同伦类型，以及利用这些集及其族进行运算的算法复杂性。基本问题是根据其定义公式的结构复杂性来估计可定义集的拓扑复杂性。算法实代数几何和拓扑o-极小性的最新发展表明，对于可定义在具有Bezout型有限性质的o-极小结构中的一大类集合，可以得到这个问题的答案。值得注意的是，A.Gabrielov和N.Vorobjov提出的组合几何结构允许人们用同伦等价的可定义紧集来逼近任意可定义集，从而大大简化了对其拓扑的研究。此外，同伦限制构造允许用无量词公式定义的同伦等价单纯对象来逼近由存在量词的公式定义的集合，并利用下降谱序列来计算原始集合的拓扑不变量。这一研究将促进我们对可定义在o-极小结构中的集合的拓扑性质的理解，以及对这种集合及其族运算的算法复杂性的理解。这将为o-极小代数拓扑学提供新的工具。本研究的目的是给出半代数集(由多个实变量中的多项式之间的公式和多项式之间的公式定义)及其推广的O-极小结构中可定义集的拓扑复杂性的新的上界。给定适当的复杂性度量，例如限制多项式零点个数的Bezout定理，可定义集的拓扑复杂性取决于其定义公式的结构复杂性。最近，A.Gabrielov和N.Vorobjov提出了一种用同伦等价紧集代替一般可定义集的结构，将一个简单的组合过程应用于原始集合的定义公式。因此，一般可定义集的拓扑复杂性问题可以归结为更容易处理的紧集问题。拟议的研究将在o-极小理论、拓扑学、组合学和实代数几何之间建立新的联系。它将为实代数和解析几何中更快的计算算法的开发及其在控制理论、可视化和计算机辅助设计中的应用提供新的组合和拓扑工具。

Andrei Gabrielov proposes to investigate homotopy types of definable sets in o-minimal expansions of real closed fields, and the algorithmic complexity of operations with such sets and their families. The fundamental question is to estimate the topological complexity of a definable set in terms of the structural complexity of its defining formula. Recent developments in algorithmic real algebraic geometry and topological o-minimality suggest that an answer to that question can be obtained for a wide class of sets definable in o-minimal structures with the Bezout-type finiteness property. Notably, a combinatorial-geometric construction suggested by A. Gabrielov and N. Vorobjov allows one to approximate arbitrary definable sets by homotopy equivalent definably compact sets, simplifying considerably the study of their topology. Furthermore, homotopy colimit construction allows one to approximate a set defined by a formula with existential quantifiers by a homotopy equivalent simplicial object defined by a quantifier-free formula, and to employ the descent spectral sequence to compute topological invariants of the original set. The proposed research will advance our understanding of the topological properties of the sets definable in o-minimal structures, and of the algorithmic complexity of operations with such sets and their families. It will provide new tools for the o-minimal algebraic topology.The goal of the proposed research is to develop new upper bounds on the topological complexity of semialgebraic sets (defined by formulas with equations and inequalities between polynomials in several real variables)and their generalizations known as definable sets in o-minimal structures. Given an appropriate measure of complexity, such as Bezout theorem bounding the number of zeros of a polynomial, the topological complexity of a definable set depends on the structural complexity of its defining formula. Recently A. Gabrielov and N. Vorobjov suggested a construction replacing a general definable set with a homotopy equivalent compact set, applying a simple combinatorial procedure to the defining formula of the original set. Thus the problem of the topological complexity of the general definable sets can be reduced to the more tractable problem for the compact sets. The proposed research will establish new connections between o-minimal theory, topology, combinatorics, and real algebraic geometry. It will provide new combinatorial and topological tools for development of faster computational algorithms in real algebraic and analytic geometry and its applications in control theory, visualization, and computer-aided design.