Homotopy, Complexity and O-Minimality

同伦、复杂性和 O-极小性

• 批准号: 0801050
• 负责人: Andrei Gabrielov
• 金额: $ 21.9万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-06-01 至 2012-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0801050&HistoricalAwards=false
• 关键词: Homotopy; Complexity; Minimality

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.

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