- #1
goraemon
- 67
- 4
Homework Statement
1. Give a language L that cannot be decided by a TM using space O(log n) and time less than n on inputs of length n. The language L should be decidable by some TM. Assume the TM has a binary input alphabet.
Homework Equations
Undecidability, Turing Machines, Languages...
The Attempt at a Solution
At first I was tempted to just answer with something like the following: The Travelling Salesman Problem, aka Langauge = { <G, k> | there exists a path that visits every vertex of graph G exactly once and has total path length <= k}. 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).
But I'm having some doubts as to whether this is the right way to go, especially after reading about space hierarchy theorem and the proof for it. The proof for that theorem lays out some language like, L = { <M, 1^n> | M rejects its own input <M> using <= f(n) space and <= 2^f(n) time }
I'm wondering whether my answer to the problem above should be in similar vein, and if so, am unsure how I would go about it. Would appreciate some pointers.