On time-space classes and their relation to the theory of real addition
Anni R. Bruss, Albert R. Meyer · 1978
A new lower bound on the computational complexity of the theory of real addition and several related theories is established: any decision procedure for these theories requires either space 2εn or nondeterministic time 2εn2 for some constant ε > O and infinitely many n.