Is Space a Stronger Resource than Time? Positive Answer for the Nondeterministic at-Least-Quadratic Time Case

Nicola Caporaso

We show that all languages accepted in time f(n) >= n^2 can be accepted in space O(f(n)^{1/2})_and_ in time O(f(n)). The proof is carried out by simulation, based on the idea of gu…