===========================================================================
CSC 363H               Exercise 8 -- 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.  [6 marks]

    (a) [3 marks]

        1 mark:  correct argument that if PATH is NP-complete, then P = NP
        2 marks:  correct argument that if P = NP, then PATH is NP-complete

    (b) [3 marks]

        2 marks:  correct reduction PATH <=p SUBSET-SUM
        1 mark:  correct argument this does not imply P = NP

B.  [6 marks]

    1 mark:  correct high-level argument HALF-HAMPATH in NP (clear
        statement of certificate and runtime sufficient)
    2 marks:  clear attempt to construct specific input for HALF-HAMPATH
        from general input for some NP-hard language A, then argue
        construction takes polytime and works (i.e., structure of answer is
        correct, even if idea is completely wrong)
    1 mark:  clear and correct construction
    2 marks:  correct argument construction works

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

A.  1.  Many times I was not able to understand what the students were
        doing.  I would advise them, anytime they are writing an argument,
        that they read it again as if they were the marker.  I know that
        this is difficult to do, since they have to pretend that they are
        someone else (and erase temporarily some thoughts they have in
        mind) and then check if what they have written makes sense.  I am
        saying this, because many times I am feeling that students have
        more things in mind than what they actually write.  Unfortunately
        they are marked according to what they have written and not what
        they had in mind (at least this is the case for the homeworks when
        they have the comfort of time to express themselves appropriately).
    2.  Please try to avoid referring to theorems as numbers.  The problem
        with this is that we need to know that you understand whether or
        not all of the conditions of the theorem are met before you apply
        it, so you need to state those conditions (and the conclusion)
        anyway.
    3.  To me the point of this question was to see the explicit reductions
        that make the statements true.  Even if students have proved the
        statements alternatively, I would advise them to come up with
        reductions by themselves.  This is a nice way of demystifying the
        concept of polytime reductions.
    4.  In the reduction PATH <=_p SUBSET-SUM, many students described what
        the mapping of the reduction is only when the "source" and the
        "sink" in the path instance are connected.  Their reduction is not
        well defined, since they are missing the case when the "source" and
        the "sink" are not connected.  Apart from that, the reduction could
        not be correct simply because it is based only on a yes instance.
    5.  Many students again wrote down the given information, and
        automatically implied the required statements.  As a special case
        for this, many students said that if B in NP, A in P and B <=p A,
        then B is in P.  Of course this statement is true, and it would be
        sufficient as an argument in a future course that is related to
        complexity.  However, in this course, students are expected to
        explain things at a deeper level whenever the statements they are
        using involves the material that is new for the course.  For
        example, for the previous case, it would be interesting to write
        down the algorithm that actually proves that B is in P.  This way,
        they could both learn the material better, and convince the marker
        that they understand the material.


B.  1.  Most of the students came up with a wrong reduction.  In every case
        I wrote down a counterexample proving them wrong.  More
        specifically, for any wrong reduction f, I came up with w, such
        that f(w) in 363SUM, but still w not in SUBSET-SUM.
    2.  One of the most serious mistakes one can make designing a
        reduction, is the reduction to be exponential.  For this reason,
        we cannot solve in the reduction the problem we are reducing from
        (unless that problem can be solved in polytime).  For example, if
        we want to reduce SUBSET-SUM to 363SUM, and starting with an
        instance <S,t> of SUBSET-SUM, we want to find S', the instance of
        363SUM, we are not allowed to use a subset T of S that sums up to
        t.  The reason for this is that we do not know how to do this in
        polynomial time (otherwise P=NP, for which we do not have a proof
        yet -- and the consensus is that it is not true).