A Measure of Space for Computing over the Reals

Details A Measure of Space for Computing over the Reals A Measure of Space for Computing over the Reals

2006-03-03

arxiv.org/abs/cs/0603017v2

Logical Approaches to Computational Barriers Second Conference on Computability in Europe, CiE 2006, Royaume-Uni (2006) 231-24

Computer Science

Computational Complexity

Scientific paper

We propose a new complexity measure of space for the BSS model of computation. We define LOGSPACE\_W and PSPACE\_W complexity classes over the reals. We prove that LOGSPACE\_W is included in NC^2\_R and in P\_W, i.e. is small enough for being relevant. We prove that the Real Circuit Decision Problem is P\_R-complete under LOGSPACE\_W reductions, i.e. that LOGSPACE\_W is large enough for containing natural algorithms. We also prove that PSPACE\_W is included in PAR\_R.

Affiliated with

Also associated with

No associations

Rating

A Measure of Space for Computing over the Reals 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 A Measure of Space for Computing over the Reals, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Measure of Space for Computing over the Reals will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-118295