VPSPACE and a transfer theorem over the reals

2007 
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 PARR of decision problems that can be solved in parallel polynomial time over thereal numbers collapses to PR. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate PR from NPR, or even from PARR.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    27
    References
    9
    Citations
    NaN
    KQI
    []