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
Contributor : Sylvain Perifel Connect in order to contact the contributor
Submitted on : Monday, June 11, 2007 - 3:50:09 PM
Last modification on : Thursday, September 29, 2022 - 2:58:07 PM
Long-term archiving on: : Thursday, April 8, 2010 - 7:36:04 PM


Files produced by the author(s)


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



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



Record views


Files downloads