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

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

2010-01-26

arxiv.org/abs/1001.4649v1

Computer Science

Computational Complexity

7 pages

Scientific paper

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 guessing the sequences of internal states of the simulated TM when entering certain critical cells, whose location is also guessed. Our method cannot be generalised easily to many-tapes TMs, and in no case can it be relativised.

Affiliated with

Also associated with

No associations

Rating

Is Space a Stronger Resource than Time? Positive Answer for the Nondeterministic at-Least-Quadratic Time Case does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Is Space a Stronger Resource than Time? Positive Answer for the Nondeterministic at-Least-Quadratic Time Case, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Is Space a Stronger Resource than Time? Positive Answer for the Nondeterministic at-Least-Quadratic Time Case will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-644513