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

    1 mark:  clear attempt to describe reduction function for A <=p C
        based on reduction functions for A <=p B and B <=p C
    1 mark:  correct reduction function for A <=p C
    1 mark:  correct complexity analysis of reduction function

B.  [3 marks]

    1 mark:  correct justification for A <=p SAT (A in NP and SAT NP-hard),
        and same in the other direction [0.5 for high-level argument "any
        two NP-complete languages reduce to each other" without details]
    1 mark:  correct conclusion (with justification) from "A <=p SAT"
    1 mark:  correct conclusion (with justification) from "SAT <=p A"

C.  [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.  The crucial part in this question was to argue that since a TM runs
        in polynomial time p(n), then its output cannot have size more than
        the running time.  Then, for any other polynomial q(n), q(p(n))
        remains a polynomial.  The fact that for two polynomials p(n),q(n),
        their product is still a polynomial is completely irrelevant.
    2.  Whoever did not mention complexity analysis lost 1 mark.


B.  Most of the proofs here where not clear.  It is important that a proof
    is well written and structured while most of them where cloudy.  Have
    in mind that whenever you want to imply something, you need to state
    precisely which part of the hypothesis you are using and which part of
    the requirements you are proving.  For example, copying down all
    hypotheses and writing that they imply the required logical statements,
    is not a proof.  Moreover, do not use phrases like "we know it from
    lecture notes" unless you mention exactly what is know from lecture
    notes.  I am saying this because many arguments seem to me like they
    are superficially reduced to theorems that just exist and nobody knows
    what they say.  Moreover I would suggest that (especially when the
    statements of the theorems are short) students write down the proofs,
    instead of referring just to numbers (e.g., theorem 7.36).  A reason
    for this is that students also need to check whether the conditions of
    the theorem holds (and then apply it).

C.  1.  I encountered many times what is described in sample solutions of
        Francois as a common mistake 2 (construction depends on solving the
        instance for A, which cannot be done in polytime if A is NP-hard).
    2.  In a reduction we have to start with an arbitrary input and not
        with an element in the language.  For example if we want to show
        that A <=p B, then we start with an input x for the problem A (and
        not with x in A).  After we describe f(x) (where f is the polytime
        reduction), THEN we argue that x in A iff f(x) in B.
    3.  Verifiers have to run in deterministic polynomial time.  Verifiers
        that characterize NP are not allowed to be nondeterministic.  That
        is, either describe a deterministic verifier or describe a
        nondeterministic decider, but do not try to do both at once!
    4.  When a question asks to prove that A <=p B, then one *consequence*
        of what we do is to show how to solve A in polynomial time, if B is
        polytime solvable.  However, a proof for this question is just the
        reduction.  There is no need to give the details on how to solve A
        given some algorithm for B (it's irrelevant).
    5.  Many students came very close to the right reduction, but
        interestingly, at the last moment they were adding more edges that
        ruined their construction.  For some reason they were not feeling
        comfortable with disconnected graphs.  Why?