Topological complexity and quantitative o-minimality

摘要奖：DMS-0245628主要研究人员：Andrei Gabrielov主要研究实数上o-极小结构中可定义集的拓扑复杂性，特别是实半代数集和次Pfaffian集的拓扑复杂性。这项研究将基于计算这类集合的同调的新工具：与满射相关的谱序列，以及单参数族上的相对闭运算。这些结果将应用于定量o-极小问题：在实数的o-极小扩张中可定义集上的拓扑、几何和代数运算的复杂性。所提出的研究结果将促进o-极小理论的定量和算法方面的发展。作为更广泛的影响，这些结果将为计算机算法对稀疏多项式、指数函数和三角函数的运算提供理论基础。由代数方程组和不等式组(半代数集)定义的对象出现在许多数学及其应用领域，如控制理论、机器人学和计算机辅助设计。了解对这类对象的复杂操作对于开发高效的计算机算法至关重要。在许多实际重要的情况下，亚半代数集的定义中的多项式是稀疏的，即具有很少的非零系数。稀疏性不能通过许多自然操作来保持，例如投影子空间或闭包。所提出的研究结果将允许人们在保持原始多项式的稀疏性的情况下，通过某些辅助集的复杂性来评估半代数集上的运算的复杂性。这可能会极大地提高此类运算的复杂性上限，从而导致更高效、更快的计算机算法。

AbstractAward: DMS-0245628Principal Investigator: Andrei GabrielovThe principal investigator proposes to investigate thetopological complexity of definable sets in o-minimal structureson the real numbers, in particular, of the real semialgebraic andsub-Pfaffian sets. This research will be based on the new toolsfor computing homology of such sets: a spectral sequenceassociated with a surjective map, and the relative closureoperation on one-parametric families. The results will beapplied to the problems of quantitative o-minimality: thecomplexity of topological, geometric and algebraic operations ondefinable sets in o-minimal extensions of the real numbers. Theresults of the proposed research will advance quantitative andalgorithmic aspects of the o-minimal theory. As a broaderimpact, these results will provide a theoretical basis forcomputer algorithms for operations on sparse polynomials,exponential and trigonometric functions.Objects defined by systems of algebraic equations andinequalities (semi-algebraic sets) appear in many areas ofmathematics and its applications, such as control theory,robotics, and computer-aided design. Understanding thecomplexity of operations on such objects is crucial fordeveloping efficient computer algorithms. In many practicallyimportant cases, polynomials in the definition of asemi-algebraic set are sparse, i.e., have few non-zerocoefficients. Sparsity is not preserved by many naturaloperations, such as projection to a subspace or closure. Theresults of the proposed research would allow one to evaluate thecomplexity of operations on semi-algebraic sets in terms of thecomplexity of some auxiliary sets, retaining sparsity of theoriginal polynomials. This may drastically improve upper boundson the complexity of such operations, leading to more efficient,faster computer algorithms.