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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
27
References
9
Citations
NaN
KQI