Counting complexity classes for numeric computations I : Semilinear sets

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

10 Scopus Citations
View graph of relations

Author(s)

  • Peter Bürgisser
  • Felipe Cucker

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)227-260
Journal / PublicationSIAM Journal on Computing
Volume33
Issue number1
Publication statusPublished - Nov 2003

Abstract

We define a counting class #Padd 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 FPARadd-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.

Research Area(s)

  • Betti numbers, Counting complexity, Euler characteristic, Real complexity classes

Citation Format(s)

Counting complexity classes for numeric computations I: Semilinear sets. / Bürgisser, Peter; Cucker, Felipe.
In: SIAM Journal on Computing, Vol. 33, No. 1, 11.2003, p. 227-260.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review