2
$\begingroup$

I'm learning about time and space complexity involving Turing Machines at the moment, and would really like some concrete examples of specific languages that belong (or don't belong) to certain classes of time / space hierarchies. For example, what are some examples of a decidable language that can't be decided by a TM using space O(log n) and time less than n, on inputs of length n?

Might the Travelling Salesman Problem be an example to the above question, since I think the brute-force algorithm for TSP would take space O(n) (store the current shortest path, and compare it with each new path that's being explored)?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ "Is the parity odd?" can't be decided in time less than n, since deciders for it need to read the whole input. ​ ​ $\endgroup$ – user12859 Feb 28 '16 at 19:39
3
$\begingroup$

Look up the time hierarchy and space hierarchy theorems. They give examples of languages which can be computed using $f(n)$ time (or space), and require more or less $f(n)$ time (or space). These languages are basically the following:

Descriptions of Turing machines that halt after time $f(n)$ (after using space $f(n)$).

Perhaps you won't consider these languages natural. Unfortunately, the best lower bounds known for natural languages are currently only $\Omega(n)$ (for time) and probably even worse for space. However, it is conjectured that NP-hard problems require exponential time (this is known as the Exponential Time Hypothesis).

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.