World's most popular travel blog for travel bloggers.

[Answers] Examples of languages not decidable by a TM using certain upper bounds on space/time

, , No Comments
Problem Detail: 

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)?

Asked By : user3280193

Answered By : Yuval Filmus

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).

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback