HW#3 --- last modified February 10 2019 21:57:21..
Solution set.
Due date: Oct 31
Files to be submitted:
Hw3.zip
Purpose:To gain experience with diagonalization techniques. To learn more about
completeness techniques.
Related Course Outcomes:
The main course outcomes covered by this assignment are:
LO3 -- Show the completeness of a complete problem for each of these classes.
LO8 -- Exhibit a relativized separation (oracle result) of complexity classes for standard classes such as P and NP.
Specification:
This homework consists in doing the following problems:
- Prove the general case of the deterministic time hierarchy theorem presented in class.
- Prove the definition of H(n) in Ladner's theorem implies an `O(n^3)`-time algorithm to compute `H(n)` from `n`.
- Imagine that we expand the definition of CNF to include clauses of the form `A(x_1, ..., x_n)` for some language `A`. This clause is true
if under a variable assignment the string represented by `x_1 ...x_n` is in the language `A`. Let `SAT^A` denote the problem of determining if a set of CNF clauses expanded with `A` clauses is satisfiable. Prove this problem is `NP^A`-complete. Show there exists an `A` such that `SAT^A` is not in `P^A`.
- Show that 2SAT is in NL.
- Show that `TQBF_k` (the problem of determining if a `k`-alternation quantified boolean formula with outermost existential `exists` is true) is `Sigma_k^p`-complete under
logspace reductions. Show `TQBF` is PSPACE-complete under logspace reductions.
On the day your homework is due I will ask each group to present one problem to me in class.
If you scored above 8 on Hw2 and you work for Hw3 with someone who scored below 8 on Hw2, I will give you a 1pt bonus. Similarly, if you scored below 8 on Hw2 and you work for Hw3 with someone who scored above 8 on Hw2, I will give you a 1pt bonus. Be advised though that all group members must be prepared to answer any question on class presentation day.
Point Breakdown
Five problems above (1.5 pts each - 1.5pts, completely correct; 1pt, missing minor details, 0.5pt, on the right track; 0 confused or wrong. |
7.5pts
|
Class presentation (Write-up clear, 1.5pts; all group members could answer brief questions about the problem intelligently, 1pt). |
2.5pts
|
Total | 10pts |
|