VPSPACE and a transfer theorem over the complex field - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

VPSPACE and a transfer theorem over the complex field

(1) , (1)
1

Abstract

We extend the transfer theorem of [KP2007] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of computation over C. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main result 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 complex field 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 P from NP over C, or even from PAR.
Fichier principal
Vignette du fichier
complex_rr.pdf (210.8 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

ensl-00153701 , version 1 (11-06-2007)

Identifiers

Cite

Pascal Koiran, Sylvain Perifel. VPSPACE and a transfer theorem over the complex field. 2007. ⟨ensl-00153701⟩
882 View
338 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More