VPSPACE and a transfer theorem over the complex field
| dc.creator | Koiran, Pascal | |
| dc.creator | Perifel, Sylvain | |
| dc.date | 2007-06-11 | |
| dc.date.accessioned | 2026-07-07T08:04:56Z | |
| dc.date.available | 2026-07-07T08:04:56Z | |
| dc.description | 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. | |
| dc.description | 14 pages | |
| dc.identifier | https://arxiv.org/abs/0706.1477 | |
| dc.identifier | http://arxiv.org/abs/0706.1477 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/130141 | |
| dc.subject | Computational Complexity | |
| dc.title | VPSPACE and a transfer theorem over the complex field | |
| dc.type | text |