| Abstract | : | Two decades ago, Blum, Shub and Smale (BSS) proposed an algebraic variant of Turing Machines where tape cells can store real or complex numbers.
In this talk, we give a brief overview of the BSS model of computation and complexity classes.
Defining right notion of space is a challenging and an unfinished task for the BSS model of real computation.
We consider the of weak-space defined by Nauraois (2007).
For weak-space bounded, division-free computations over BSS machines over complex numbers with =?0 tests, we show the following:
1) The Boolean part of the weak log-space class is contained in the deterministic log-space, i.e. BP(LOGSPACE_W)subseteq DLOG.
2) There is a set Lin NC^1_C that cannot be decided by any deterministic BSS machine whose weak-space is bounded above by a polynomial in the input length,
i.e., NC^1_C
otsubseteq PSPACE_W.
This is a joint work with Pushkar Joglekar and Siddhartha Sivakumar. |
