VPSPACE and a Transfer Theorem over the Reals

Abstract : 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.
Type de document :
Pré-publication, Document de travail
Full version of the paper (appendices of the first version are now included in the text). 2007
Liste complète des métadonnées

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00103018
Contributeur : Sylvain Perifel <>
Soumis le : mercredi 31 janvier 2007 - 15:14:37
Dernière modification le : mardi 24 avril 2018 - 13:52:21
Document(s) archivé(s) le : mardi 21 septembre 2010 - 12:30:46

Fichiers

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

Identifiants

Collections

Citation

Pascal Koiran, Sylvain Perifel. VPSPACE and a Transfer Theorem over the Reals. Full version of the paper (appendices of the first version are now included in the text). 2007. 〈ensl-00103018v2〉

Partager

Métriques

Consultations de la notice

368

Téléchargements de fichiers

110