Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
A Measure of Space for Computing over the Reals

Speaker: Paulin Jacobe de Naurois
Author(s): Paulin Jacobe de Naurois
Slot: Array, 11:30-11:50, col. 4


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. 

websites: Arnold Beckmann 2006-07-04