Subanalytic Sets, Pfaffian Functions, and Complexity of Quantifier Simplification

亚解析集、普法夫函数和量词简化的复杂性

• 批准号: 9704745
• 负责人: Andrei Gabrielov
• 金额: $ 7.7万
• 依托单位: Purdue Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-06-01 至 2000-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9704745&HistoricalAwards=false
• 关键词: Subanalytic; Sets; Pfaffian; Functions; Complexity

A. Gabrielov proposes to continue research in two closely related areas: the theory of subanalytic sets, with applications to quantifier elimination and simplification problems, and the theory of Pfaffian functions (analytic functions satisfying systems of Pfaffian differential equations with polynomial coefficients), with applications to o-minimality and computational complexity. The goal of this research is to find an effective estimate of complexity of the ``quantifier simplification'' for expressions with Pfaffian functions, i.e., replacing an expression with existential and universal quantifiers by an equivalent expression without universal quantifiers. This includes estimates of the complexity of different operations with semi- and sub-Pfaffian sets, such as the frontier, closure, stratification, and resolution of singularities. Modern computer algebra qystems allow one to perform on a computer many operations with algebraic equations and inequalities previously considered the domain of abstract algebraic geometry. The results can be applied to such practical problems as visualisation, robotics, and coding theory. The complexity of computer codes performing these operations becomes a practically important problem. This complexity usually grows quickly with the degree of polynomials. A new approach to reduce computational complexity lies in the Pfaffian theory studying a class of non-algebraic functions with global finiteness properties similar to the properties of algebraic functions. The complexity of a polynomial considered as a Pfaffian function depends only on the number of its non-zero monomials (or, more generally, on the complexity of a formula representing this polynomial) independent of its degree. Exponential and trigonometric functions, and many special functions, are Pfaffian, too. Thus Pfaffian methods, when applicable, allow one to produce fast computer codes for computations with simple algebraic, exponential and trigonometric formulas, possibly of a high degree.

加布里埃洛夫建议继续在两个密切相关的领域进行研究：次分析集理论，应用于量词消除和简化问题，以及Pfaffian函数理论(满足具有多项式系数的Pfaffian微分方程组的解析函数)，应用于o-最小性和计算复杂性。本研究的目的是对具有Pfaffian函数的表达式的“量词简化”的复杂性进行有效的估计，即用没有全称量词的等价表达式来替换带有存在和全称量词的表达式。这包括对具有半和次Pfaffian集的不同运算的复杂性的估计，例如边界、闭合、分层和奇点的分解。现代计算机代数系统允许人们用以前被认为是抽象代数几何领域的代数方程和不等式在计算机上执行许多运算。研究结果可应用于可视化、机器人学、编码理论等实际问题。执行这些操作的计算机代码的复杂性成为一个实际重要的问题。这种复杂性通常随着多项式次数的增加而迅速增长。一种降低计算复杂性的新方法在于Pfaffian理论，它研究一类具有类似于代数函数性质的全局有限性质的非代数函数。被认为是Pfaffian函数的多项式的复杂性只取决于它的非零单项式的个数(或者，更一般地，取决于表示该多项式的公式的复杂性)，而与它的次数无关。指数函数和三角函数以及许多特殊函数也是Pfaffian函数。因此，在适用的情况下，Pfaffian方法允许产生快速的计算机代码，用于使用简单的代数、指数和三角公式进行计算，可能是高度的。