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

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00153701
Contributor : Sylvain Perifel Connect in order to contact the contributor
Submitted on : Monday, June 11, 2007 - 3:50:09 PM
Last modification on : Saturday, September 11, 2021 - 3:17:23 AM
Long-term archiving on: : Thursday, April 8, 2010 - 7:36:04 PM

Files

complex_rr.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

878

Files downloads

323