A Measure of Space for Computing over the Reals
<|reference_start|>A Measure of Space for Computing over the Reals: 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.<|reference_end|>
@article{de naurois2006a,
    title={A Measure of Space for Computing over the Reals},
    author={Paulin Jacob'e De Naurois (LIPN)},
    journal={Logical Approaches to Computational Barriers Second Conference on
  Computability in Europe, CiE 2006, Royaume-Uni (2006) 231-240},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0603017},
    primaryClass={cs.CC}
}