Complexity of operations with Pfaffian and Noetherian functions and effective o-minimality

A. Gabrielov建议继续研究Pfaffian和Noetherian函数（满足多项式系数的偏微分方程组的解析函数）的理论，并将其应用于量词消除、0极小性和计算复杂性。本研究的目的是建立在实域上对Pfaffian函数及其表达式所定义集合的代数几何运算复杂度的有效上界。这可以看作是Pfaffian函数的0 -极小理论的一个定量的、有效的版本。对于全局o-极小性失效的noether函数，目标是开发该理论的局部实的和复杂的类似物。现代计算机代数系统允许人们在计算机上执行许多代数方程和不等式的运算，这些运算以前被认为是抽象代数几何的领域。最新的成果之一是求解代数方程组奇点的算法。研究结果可以应用于可视化、机器人和编码理论等实际问题。执行这些操作的计算机代码的复杂性成为一个实际的重要问题。这种复杂性通常随着多项式的程度而快速增长。Pfaffian理论允许人们显著地降低“少多项式”运算的计算复杂性，“少多项式”是指具有很少非零项的高阶多项式。本研究的目标是将普氏理论与奇异点的算法解决相结合，以发展对少数多项式系统的有效计算程序。

A. Gabrielov proposes to continue research on the theory of Pfaffian and Noetherian functions (analytic functions satisfying systems of partial differential equations with polynomial coefficients), with applications to quantifier elimination, o-minimality, and computational complexity. The goal of this research is to establish effective upper bounds for the complexity of algebro-geometric operations on Pfaffian functions and the sets defined by expressions with such functions in the real domain. This can be considered as a quantitative, effective version of the o-minimal theory of Pfaffian functions. For Noetherian functions, where global o-minimality fails, the goal is to develop local real and complex analogs of this theory.Modern computer algebra systems allow one to perform on a computer many operations with algebraic equations and inequalities previously considered the domain of abstract algebraic geometry. One of the latests achievements is an algorithm for the resolution of singularities of systems of algebraic equations. The results can be applied to such practical problems as visualisation, robotics, and the coding theory. The complexity of computer codes performing these operations becomes a practically important problem. This complexity usually grows fast with the degree of polynomials. The Pfaffian theory allows one to significantly reduce the computational complexity of operations on "fewnomials" - polynomials of high degree with few non-zero terms. The goal of the proposed research is to combine the Pfaffian theory with the algorithmic resolution of singularities, in order to develop efficient computational procedures for fewnomial systems.