VPSPACE and a Transfer Theorem over the Reals
| Autor: | Sylvain Perifel, Pascal Koiran |
|---|---|
| Přispěvatelé: | Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL) |
| Rok vydání: | 2009 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
FOS: Computer and information sciences General Mathematics algebraic complexity 0102 computer and information sciences Computational Complexity (cs.CC) 01 natural sciences Theoretical Computer Science Combinatorics 0101 mathematics Time complexity Computer Science::Databases PSPACE Real number Mathematics Discrete mathematics computational complexity 010102 general mathematics Order (ring theory) Computer Science - Computational Complexity Computational Mathematics Transfer (group theory) Computational Theory and Mathematics 010201 computation theory & mathematics Algebraic complexity Blum-Shub-Smale model Valiant's model |
| Zdroj: | computational complexity. 18:551-575 |
| ISSN: | 1420-8954 1016-3328 |
| DOI: | 10.1007/s00037-009-0269-1 |
| Popis: | 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. Comment: Full version of the paper (appendices of the first version are now included in the text) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink