2006/10/03 by Pascal Koiran, Koiran, Pascal, Sylvain Perifel +1
Computer Science · #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Methods in Verification #Logic, Reasoning, and Knowledge #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0610009
Full version of the paper (appendices of the first version are now included in the text)
openalex publication_date 2006/10/03 · arxiv created 2007/02/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.