Subanalytic Sets, Pfaffian Functions, and Complexity of Quantifier Simplification

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

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.