Homework 11

General Comments

• Problems are taken from the textbook unless otherwise noted.
• For full credit, provide context for each problem, show all calculations, and explain your work/answers.
• Numbers and/or algebra by themselves are not enough.
• You will lose a significant amount of credit if you do not show enough work/context for your answers.
• Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• You must indicate any assistance you had on an assignment as specified on the Policies page.

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