----------------------------------------------------- CSC363H1 -- Fall 20007 -- Assignment 2 Marking Scheme ----------------------------------------------------- Basic guidelines: - Be picky: students are responsible for showing that they understand, so take marks off for anything incomplete or ambiguous -- if you're not sure something is correct and you can't tell quickly, then the student either didn't have the right idea or didn't explain it well so take marks off (students can always request remarking later) -- at the same time, don't go overboard: if something looks reasonable, give the benefit of the doubt. - Give feedback: use codes/keywords for common errors and keep a list of how they were marked, give more detailed feedback for unusual solutions; in addition, you may want to use letter codes to refer to specific points of the marking scheme. 1. [10 marks] 4: clear attempt to show A <=p A_TM for a specific NP-complete A, or for a generic A in NP; correct outline of reduction (start with arbitrary input x for A, construct specific input for A_TM, argue construction takes polytime, argue x in A iff in A_TM) 4: correct construction (making appropriate use of A in NP) and argument of correctness 2: correct, specific bound on reduction's runtime Marker's Comments: a. Despite the explicit request of the question to write down a time bound for the reduction, many students omitted to do so. b. Formally the answer involved the following crucial step. Start with an instance x of some NP complete language L, and construct an instance (M,y) of A_TM, such that x in L iff (M,y) in A_TM (M,y depends on x and L). Surprisingly, many students were outputting just a TM, or even worse, some of them did not even start with some arbitrary x. I conclude that they either are misunderstanding the definition of A_TM or the definition of reduction. 2. [10 marks] 3: clear attempt to show SL in NP by giving explicit verifier/NTM; clear attempt to show SL is NP-hard by showing A <=p SL for specific NP-hard A (expect most students to pick Vertex Cover), including correct outline of reduction (see above) 1: correct verifier for SL (even if minimal, e.g., "certificate = set of servers" -- important thing is argument that verification takes polytime) 2: correct reduction 4: correct proof of correctness of reduction Note: For "half-correct" reductions (where correctness works in one direction but not the other), give 1/2 marks for the reduction and at most 2/4 for the argument of correctness. Marker's Comments: a. Sometimes even the verifier was incorrect. Assuming that students know what a verifier should do, I conclude that they do not pay attention to the question (there they can find the definition of the problem). It is too bad that they are losing marks for such reasons. b. A reduction involves two steps. Suppose we are reducing A to B. Then given x, we construct f(x) such that x in A iff f(x) in B. To prove that our construction works, first we start with an arbitrary x in A and show that f(x) in B. Then we start with an arbitrary element f(x) in B (in the mapping of f) and show that x in B. Of course this is equivalent in proving that if x not in A then f(x) not in B. For the problem we are dealing with, this translates to the following: if the graph G does not have a vertex cover of size k, then G' (the map of the reduction) does not have k' servers. Say for simplicity that k=k' and G' has at least that many nodes as G plus some more (there exist such a reduction -- see sample solutions). So the intention is that any vertex of a valid cover of G corresponds to a server of G'. Now go back to the proof of correctness of the reduction. It would be fine if you could argue that if G does not have vertex cover of size k , then G' does not have a set of appropriate servers. However, starting with a particular set of k vertices in G (that are not a vertex cover) the only thing that you can say is that the corresponding vertices in G' do not form an appropriate set of servers. However you do not know anything about other sets of k servers. In summary, I want to say that sometimes proving the contrapositive is not easier (at least here this is the case in my opinion), and moreover it might be tricky. c. Many reductions were wrong. In every case i wrote down a counteraxmple (see also comments of the last exercise). d. Many students forgot to describe the running time of the reduction. This is an important step of the proof. 3. [15 marks] 5: clear attempt to show A is coNP-complete iff ~A is NP-complete, for arbitrary language A; clear attempt to show ~EQ is NP-complete (with correct outline of reduction -- see above) 3: correct argument that A is coNP-complete iff ~A is NP-complete (can be minimal but must be present) 1: correct verifier for ~EQ 2: correct reduction 4: correct proof of correctness of reduction Note: Deal with "half-correct" reductions as indicated above. Marker's Comments: a. The most common mistake here was that students were mapping a formula F to . This is wrong because no matter what F is, is always in EQ^c. 4. [10 marks] 2: clear attempt to give an explicit algorithm for MSL, making use of subroutine that solves instances of SL; clear attempt to analyze runtime of algorithm and argue its correctness 4: reasonable algorithm to solve MSL 2: correct analysis of algorithm's runtime 2: correct argument of correctness for algorithm Note: Be lenient when marking the algorithm and its proof of correctness! Give roughly 80% for reasonable attempts that are incorrect for subtle reasons, but for which students have tried to argue correctness (and missed the flaws); roughly 90% for reasonable attempts followed by an admission that the algorithm doesn't work (and an explanation of why it fails); 100% only for correct algorithms -- we want to reward students who managed to solve it correctly, without being harsh on students who failed but made a reasonable attempt. Marker's Comments: a. When you are proving self reducibility and you are analyzing the running time of your algorithm, it would be nice to start with the assumption that you just know the running time of the algorithm that solves the decision problem, rather than assuming that it is polynomial. The reason is that it is important to also see how the running time of the final algorithm compares to the running time of the algorithm for the decision problem, and not just argue that the running time of the former is polynomial. b. Consider the reduction proposed in the sample solutions. If you omit the correction phase in which we erase unnecessary edges, then the reduction is wrong (that "small" detail made the question difficult). This observation is thanks to a student :) . Here is a counterexample: c b \ / d--h--g--a / \ e f Take d=1 and k=2. This is a Yes instance since vertices h,g is an appropriate set of servers. Moreover this is a unique solution. However if you erase one of them (say h), together with every vertex it is connected to (c,d,e, and g), then you come up with a set of three isolated vertices (b,a,f) that cannot be served with one more server. 5. (a) [8 marks] 2: clear attempt to give polyspace algorithm, argue its correctness, and analyze its complexity 3: correct algorithm 1: correct argument of correctness 2: correct analysis of space complexity Marker's Comments: No comments here. Most students did it well. 5. (b) [7 marks] 2: clear attempt to give polytime algorithm/verifier for OPT/~OPT, then argue this implies polytime decider for OPT (including correct outline of verifier) 3: correct verifier for ~OPT 2: correct use of assumption P = NP to argue verifier is polytime and to conclude OPT in P Marker's Comments: No comments here. Most students did it well.