Counting complexity classes for numeric computations I: Semilinear sets

摘要

We de. ne a counting class #P-add in the Blum-Shub-Smale setting of additive computations over the reals. Structural properties of this class are studied, including a characterization in terms of the classical counting class #P introduced by Valiant. We also establish transfer theorems for both directions between the real additive and the discrete setting. Then we characterize in terms of completeness results the complexity of computing basic topological invariants of semilinear sets given by additive circuits. It turns out that the computation of the Euler characteristic is FPadd#Padd-complete, while for fixed k the computation of the kth Betti number is FPAR(add)-complete. Thus the latter is more difficult under standard complexity theoretic assumptions. We use all of the above to prove some analogous completeness results in the classical setting. [References: 45]