VPSPACE and a transfer theorem over the complex field
| Autor: | Pascal Koiran, Sylvain Perifel |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Class (set theory)
Polynomial Algebraic complexity General Computer Science Computational complexity theory Model of computation Theoretical Computer Science Computational complexity Combinatorics Transfer (group theory) Order (group theory) Valiant’s model Time complexity Blum–Shub–Smale model PSPACE Mathematics |
| Zdroj: | MFCS |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2009.08.026 |
| Popis: | We extend the transfer theorem of [14] 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 PARC of decision problems that can be solved in parallel polynomial time over the complex field collapses to PC. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate PC from NPC, or even from PARC. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect