Homework 11
Last updated: Tue, 7 Dec 2021 16:54:48 -0500
Out: Wed Dec 08, 00:00 EST Due: Tue Dec 14, 23:59 EST
This assignment explores space complexity and the hierarchy theorems.
Homework Problems
Modified Read-only Input, Two-Tape TM (6 + 4 = 10 points)
NL contained in P (6 points)
NL is coNL (6 points)
Time Constructibility (6 points)
No Log Algorithm (10 points)
README (2 point)
Total: 40 points
Submitting
Submit your solution to this assignment in Gradescope hw11. Please assign each page to the correct problem.
A submission must include a README containing the required information, in addition to the solution to the problems.
1 Modified Read-only Input, Two-Tape TM
Prove that the modified read-only input, two-tape TM used to model log space algorithms is equivalent to the normal one-tape TM, where equivalent means that they accept the same language. (This proof requires proving two statements.)
Does your answer above still hold if equivalence of two machines additionally requires that they use the same amount of space? Explain why or why not.
2 NL contained in P
Prove that \textbf{NL} \subseteq \textbf{P}.
Your proof must begin with the lines from lecture. To complete the proof, give a justification for each line.
3 NL is coNL
Prove that \textbf{NL} = \textbf{coNL}.
Your proof must begin with the lines from lecture. To complete the proof, give a justification for each line.
4 Time Constructibility
Prove that n \log n is a time constructible function.
5 No Log Algorithm
Prove that Double Satisfaction problem from Homework 9 has no log time algorithm. Use the "nonexistence" recipe from lecture.