首页 | 本学科首页   官方微博 | 高级检索  
     


VPSPACE and a Transfer Theorem over the Reals
Authors:Pascal Koiran  Sylvain Perifel
Affiliation:1. LIP, école Normale Supérieure de Lyon, Université de Lyon, (UMR 5668 ENS Lyon, CNRS, UCBL, INRIA), Lyon, France
Abstract: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 \sf PAR\mathbb R\sf {PAR}_{\mathbb {R}} of decision problems that can be solved in parallel polynomial time over the real numbers collapses to \sfP\mathbb R\sf{P}_{\mathbb {R}}. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate \sfP\mathbb R\sf{P}_{\mathbb {R}} from \sfNP\mathbb R\sf{NP}_{\mathbb {R}}, or even from \sfPAR\mathbb R\sf{PAR}_{\mathbb {R}}.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号