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

点击翻译按钮获取中文摘要

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.