HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 : Wednesday, January 31, 2007 - 3:14:37 PM
Last modification on : Saturday, September 11, 2021 - 3:17:00 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 12:30:46 PM

Files

reals.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

759

Files downloads

328