The University of Melbourne • COMP90057 2020s2 • Complexity Assessment-v2
COMP90057 Advanced Theoretical Computer Science Complexity Assignment
Version 2
Second (Spring) Semester 2020
Posted on LMS Wednesday 9 September Due Monday 28 September 10:00
Your submission must be typed and be in pdf format!
Each student must submit their own individual and original work. There is a further notice about this at the end of this document. For this Assignment, you can refer only either to materials on the COMP90057 LMS pages or the textbook.
This Assignment contributes 15% towards your total mark for this subject. As a reminder, there is a hurdle on the non-final-examination component for this subject.
Proof questions
For each of these four questions, submit a carefully argued proof: remember to reference results in notes/slides/text that you rely on. Start each question on a new page.
Question 1 [2 marks] Let M be a k-tape nondeterministic Turing machine – a decider – whose time complexity function is t(n). Show that there is some 2-tape nondeterministic Turing machine that decides L(M) in time proportional to k · t(n). Hint: The nondeterminism is important.
Question 2 [4 marks] A tournament is a directed graph with the following property: for every pair of two distinct nodes {u, v}, there is either an edge u → v or an edge v → u. In a directed graph, a subset S of the vertices is a dominating set if, for every vertex v in the graph, either v ∈ S or there exists u ∈ S the edge u → v. The Dominating Set language comprises pairs ⟨G, k⟩ where G is a directed graph that has a dominating set of size at most k.
(a) [2 marks] Show that every tournament graph with n nodes, n > 1, has a dominating set of size ⌈log2 n⌉. Hint: Show that there is some vertex that dominates at least half the nodes.
(b) [2 marks] Show that if
{⟨G, k⟩ | G is a tournament and ⟨G, k⟩ ∈ Dominating Set}
is NP-complete, then NP ⊆ ∪b≥1 TIME(nb log n ).
Question 3 [1 mark] Show that RP is closed under the union operation.
Question 4 [2 marks] Harder! By referring to the Space Hierarchy Theorem, i.e., Theorem 9.3 in the textbook, or otherwise, show that NP ̸= SPACE(n4). Hint: the class NP is closed under polynomial-time reductions; what about SPACE(n4)?
Essay Question
The following essay question should start in a new page in your submission.
1
The University of Melbourne • COMP90057 2020s2 • Complexity Assessment-v2
Essay question [6 marks] Write a response to the technical report On Asymptotic Notation with Multiple Variables by Rodney Howell1.
Your response should be around 500–800 words, and should critique the approach, as well as highlight the strengths, of the report. Although you can choose your own emphasis, we recommend that your report address some or all of the following questions.
• What are some scenarios in which multivariate asymptotic notation would be helpful? That is, what are the problem settings, inputs, etc.?
• Does the critique related to Property 1 seem valid? Are there assumptions that would invalidate Howell’s argument?
• How convincing is Theorem 2.3? Does this seem to apply to a wide range of time- complexity functions?
• How useful is the solution proposed in Section 3?
• Is the buildup of Theorems 3.6, 3.7, 3.8 helpful?
Submissions
You should lodge your submission for the Complexity Assignment via the LMS. It must be
typed and be in pdf format. You must identify yourself in your submission! Administrative issues
When is late? What do I do if I am late? The due date and time are printed on the front of this document. The lateness policy is on the handout provided at the first lecture. As a reminder, the late penalty for this assessment is 2 marks per day (or part thereof) overdue. Requests for extensions or adjustment must follow the University policy (the Melbourne School of Engineering “owns” this subject), including the requirement for appropriate evidence.
Late submissions should also be lodged via the LMS, but, as a courtesy, please also email Tony Wirth when you submit late. If you make both on-time and late submissions, please consult Tony Wirth as soon as possible to determine which submission will be assessed.
Individual work You are reminded that your submission for this Assignment is to be your own individual and original work. Students are expected to be familiar with and to observe the University’s Academic Integrity policy http://academicintegrity.unimelb.edu.au/. For the purpose of ensuring academic integrity, every submission attempt by a student may be inspected, regardless of the number of attempts made.
Students who allow other students access to their work run the risk of also being penalized, even if they themselves are sole authors of the submission in question. By submitting your work electronically, you are declaring that this is your own work. The Academic Board Regulation defines student academic misconduct; at the time of posting this assignment, the regulation may be found linked from the University’s legislative framework page2.
AIW
⃝c The University of Melbourne September 2020
1 http://people.cs.ksu.edu/~rhowell/asymptotic.pdf Thanks to our student auditor Billy Price for alerting me to this.
2 https://about.unimelb.edu.au/strategy/governance/regulatory-framework/legislative-framework
2