TY - GEN
T1 - Counting complexity classes over the reals I
T2 - 14th Annual International S- posium on Algorithms and Computation (ISAAC 2003)
AU - Bürgisser, Peter
AU - Cucker, Felipe
PY - 2003
Y1 - 2003
N2 - 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 semi-linear 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 the above to prove some analogous completeness results in the classical setting. © Springer-Verlag Berlin Heidelberg 2003.
AB - 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 semi-linear 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 the above to prove some analogous completeness results in the classical setting. © Springer-Verlag Berlin Heidelberg 2003.
UR - https://www.scopus.com/pages/publications/35248888049
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-35248888049&origin=recordpage
U2 - 10.1007/978-3-540-24587-2_64
DO - 10.1007/978-3-540-24587-2_64
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 978-3-540-20695-8
T3 - Lecture Notes in Computer Science
SP - 625
EP - 634
BT - Algorithms and Computation
A2 - Ibaraki, Toshihide
A2 - Katoh, Naoki
A2 - Ono, Hirotaka
PB - Springer
Y2 - 15 December 2003 through 17 December 2003
ER -