Topological complexity and quantitative o-minimality

拓扑复杂性和定量最小性

• 批准号: 0245628
• 负责人: Andrei Gabrielov
• 金额: $ 13.05万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2006-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0245628&HistoricalAwards=false
• 关键词: Topological; complexity; quantitative; minimality

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.

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