Computations II: Algebraic and Semialgebraic Sets

Title: Computations II: Algebraic and Semialgebraic Sets

Research Question: How can we measure the complexity of computing basic topological invariants of semialgebraic and algebraic sets over the real and complex numbers, respectively?

Methodology: The authors define counting complexity classes #PR and #PC, which are based on the Blum-Shub-Smale setting of computations over the real or complex numbers. They investigate the complexity of computing the Euler characteristic and the geometric degree of semialgebraic and algebraic sets using these classes.

Results: The authors prove that the problem of computing the Euler characteristic of semialgebraic sets is FP#PRR-complete, and that the problem of computing the geometric degree of complex algebraic sets is FP#PC-complete. They also define new counting complexity classes in the classical Turing model and show that the problem of computing the Euler characteristic and the geometric degree of algebraic sets given by integer polynomials are complete in these classes. Additionally, they prove the FPSPACE-hardness of the problem of computing the kth Betti number of the zet of real zeros of a given integer polynomial, which holds with respect to both singular homology and Borel-Moore homology.

Implications: These results provide a framework for studying the complexity of functional problems in the continuous setting, which is less developed than in the discrete setting. They also offer insights into the complexity of computing basic topological invariants of semialgebraic and algebraic sets over the real and complex numbers, respectively.

Link to Article: https://arxiv.org/abs/0312007v1 Authors: arXiv ID: 0312007v1