VPSPACE and a transfer theorem over the complex field

Details VPSPACE and a transfer theorem over the complex field VPSPACE and a transfer theorem over the complex field

2007-06-11

arxiv.org/abs/0706.1477v1

Computer Science

Computational Complexity

14 pages

Scientific paper

We extend the transfer theorem of [KP2007] to the complex field. That is, we investigate the links between the class VPSPACE of families of polynomials and the Blum-Shub-Smale model of computation over C. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main result 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 complex field 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 P from NP over C, or even from PAR.

Affiliated with

Also associated with

No associations

Rating

VPSPACE and a transfer theorem over the complex field does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with VPSPACE and a transfer theorem over the complex field, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and VPSPACE and a transfer theorem over the complex field will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-179474