===========================================================================
CSC 363H               Exercise 6 -- Grading Scheme               Fall 2007
===========================================================================

As usual, take off marks for ambiguous or incorrect notation, ambiguous or
vague or incorrect claims that are not substantiated, or any other aspect
of the answer's write-up that makes it difficult or impossible to
understand.

A.  (a) [3 marks]

        2 marks:  correct algorithm to show L_1 in P
        1 mark:  correct argument L_1 in NP

    (b) [3 marks]

        2 marks:  correct verifier to show L_2 in NP
        1 mark:  reasonable argument L_2 probably not in P

B.  [4 marks]

    1 mark:  correct proof structure (for arbitrary languages A,B, describe
             verifier/NTM for A.B based on verifiers/NTMs for A and B)
    1 mark:  correct structure of verifier/NTM (i.e., what student writes
             is a reasonable description of a verifier/NTM)
    2 marks:  correct verifier, including argument that it works and runs
              in polytime

C.  [2 marks]

    2 marks:  correct argument


-----------------
Marker's Comments
-----------------

General comment (paraphrased from marker by instructor):

    Beware the difference between "...this is true because the prof said
    so," and "...this is true because it was proved in class."  The former
    does not indicate that you understand why it is true, and it could even
    be incorrect (what if the prof makes a mistake?); the latter indicates
    that you understand why the statement is true, and it is the correct
    way to reference results from class or textbooks.


A.  1.  Whoever forgot to mention whether L_1 in NP, lost 1 point.
    2.  whoever proved that L_2 in NP by saying that it is clearly true
        (without giving details) lost 1 mark.
    3.  Many students proposed the following algorithms for deciding L_2 in
        polytime.
        (a) First check whether the graph has max degree >k.  if yes
            reject, else apply Prim's (Kruskal's) algorithm.
        (b) Apply Prim's (Kruskal's) algorithm to obtain an MST.  If the
            resulting MST has max degree > k reject, else check the weight
            and decide accordingly.
        In both cases the algorithms are polynomial, however they decide
        different languages.  Algorithm (a) decides the language
            { <G,w,k> : G is a graph of bounded degree k,
                        where the MST has weight < w}.
        It is not clear to say what language algorithm (b) decides, since
        the output of Prim's (Kruskal's) algorithm is not uniquely defined
        (consider the graph with all edges having the same weight).  But
        definitely, this language is not L_2, since the fact that Prim's
        (Kruskal) algorithm outputs an MST with degree bigger than k, does
        not mean that one does not exist.
    4.  It is disappointing that many students where trying to answer the
        question without even knowing what the Minimum Spanning Tree
        problem is.  Of course the disappointing thing is not that they did
        not remember it, but that they did not try to find the definition
        of the problem.  As a result, many were giving as output a
        collection of vertices.
    5.  A few students claimed that if for some L in NP, we are able to
        show that L is in P then P=NP.  Of course this is not true.  This
        holds only if L is complete for NP.  As a counterexample of this
        statement, consider any language L decidable is polytime.  Then L
        is in NP and in P, but the statement P=NP is completely irrelevant.


B.  1.  Verifiers require two inputs.  If we want to verify whether x is in
        L (L is some language in NP), then we run the verifier on <x,w>,
        where w is some certificate of polynomial size with respect to <x>.
        Therefore there is no meaning in simulating verifiers with input
        only certificates (or only the string x).
    2.  Recall that verifiers have to run in polytime no matter what the
        input is.  For this reason, before running some algorithm on the
        input (x plus the certificate), the verifier should check that the
        certificate has the appropriate format (and size in some sense).
        For example, if we think as part of the certificate being an index
        i that we would like to range from 0 to size(x), first we should
        check that i is indeed a number in that range.  Otherwise we can
        easily force the verifier to run for exponentially many steps.


C.  The only comment here is the same as the 5th comment in part A.