VPSPACE and a transfer theorem over the complex field

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.
Type de document :
Pré-publication, Document de travail
14 pages. 2007
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00153701
Contributeur : Sylvain Perifel <>
Soumis le : lundi 11 juin 2007 - 15:50:09
Dernière modification le : mardi 16 janvier 2018 - 15:35:18
Document(s) archivé(s) le : jeudi 8 avril 2010 - 19:36:04

Fichiers

complex_rr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00153701, version 1
  • ARXIV : 0706.1477

Collections

Citation

Pascal Koiran, Sylvain Perifel. VPSPACE and a transfer theorem over the complex field. 14 pages. 2007. 〈ensl-00153701〉

Partager

Métriques

Consultations de la notice

118

Téléchargements de fichiers

68