Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00103018
Contributor : Sylvain Perifel Connect in order to contact the contributor
Submitted on : Tuesday, October 3, 2006 - 11:35:29 AM
Last modification on : Friday, September 10, 2021 - 2:34:02 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 5:32:15 PM

Files

Identifiers

Collections

Citation

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

Share

Metrics

Les métriques sont temporairement indisponibles