VPSPACE and a Transfer Theorem over the Reals

Pascal Koiran (1) , Sylvain Perifel (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that if (uniform, constant-free) VPSPACE families can be evaluated efficiently then the class PAR of decision problems that can be solved in parallel polynomial time over the real numbers collapses to P. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate over the reals P from NP, or even from PAR.

Mots clés: computational complexity; algebraic complexity; Blum-Shub-Smale model; Valiant's model

Domaines: Complexité [cs.CC]

Pascal Koiran, Sylvain Perifel. VPSPACE and a Transfer Theorem over the Reals. 2007. ⟨ensl-00103018v2⟩