Homework 11

Details

1. 7.1
2. 7.2
3. 7.3
4. If f(x) = O(g(x)), is it always the case that f(x) = o(g(x))? Explain, giving an example if appropriate. (Hint: an example is probably appropriate.)
5. Is TIME(log₂ (n)) = TIME(log₃(n))? In other words, do the functions log₂(n) and log₃(n) grow at the same rate? Explain and give the page number(s) in the textbook where you got the information.
6. If I have an algorithm that takes time n log (n) on a 7-tape Turing machine, how long will it take on a single-tape Turing machine. Make sure to express your answer properly. (Hint: Big-O). What theorem in the book did you use to answer the question?
7. True or false: If I can run an algorithm in polynomial time on a nondeterministic Turing machine, then I can run it in polynomial time on a single-tape Turing machine. Explain your answer.
8. Are the following problems in P? Justify your answers. (Hint: Theorem x.y in the book says so is good enough.)
   • PATH (Is there a path in a graph from vertex s to vertex t?)
   • The language A = {0ⁿ1ⁿ | n ≥ 1}. (Hint: A is context free.)