Subanalytic Sets, Pfaffian Functions, and Complexity of Quantifier Simplification

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

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.