CSC363H -- Fall 2005 -- Test 2 Marking Comments
=========
Q1

a. let t(n) be any function
   state the precise definition of NTIME(t(n))

   NTIME(t(n)) = {L / L is a language decided by a O(t(n)) time NDTM}

   1 p for L language
   1 p for O
   1 p for t(n)
   1 p for NDTM

   Had all sorts of variations of this. Few got it right.

For each language below, state whether Rice's Theorem applies (circle the
appropriate statement), give a brief justification for your answer, and
state the conclusion that can be drawn from your answer.

b. L1 = {<M> / M accepts all strings whose first and last characters are
         0}
   Rice's Theorem applies
   because it is a non-trivial property of languages
   so L1 is undecidable

   1 p for "applies"
   1 p for property of languages
   1 p for non-trivial
   1 p for "undecidable"

   Mostly well done. Some people got the answer wrong, or didn't justify
properly. They seem to be confused about what "trivial" means - it's not
whether the language of a machine is empty or all, it's whether there is a
machine whose language has the property, and one whose language does not
have it.

   L2 = {<M> / M loops on input 01001}

   Rice's Theorem does not apply
   because it's a machine property
   so nothing can be concluded

   1 p for "doesn't apply"
   2 p for machine property
   1 p for no conclusion

   Fewer got it right. Some people got the correct answer but justified it
by saying it is a trivial property!

Q2

Give a detailed proof that the following language is unrecognizable (your
proof will be marked on its structure as well as its content).

        L3 = {<M> / L(M)={00,11} }

Since we know that ATM-complement is unrecognizable, it suffices to show
that it reduces to L3
But its easy to reduce ATM to L3-complement, which is equivalent
So, L3-complement = {<M> / M is not a TM or L(M)<>{00,11} }
To show ATM <=m L3-complement:

define f: S* -> S* by f(<M,w) = <M'>, where
M' = "On input x
        if x in {00,11} accept
        run M on w and do the same"
f is computable, and we show <M,w> in ATM iff <M'> in L3-complement

<M,w> in ATM => M accepts w => M' accepts every x => L(M')=S*<>{00,11} =>
M' in L3-complement

<M,w> not in ATM => M does not accept w => M rejects or loops on any x but
00, 11, which are the only ones accepted => M' in L3 and therefore not in
L3-complement

(ignored the M not a TM issue)

6 p for structure of a reduction or proof by contradiction, including
good choice of unrecognizable language (only 4 if bad choice)
3 p for corerct details
3 p for proof of correctnes

Fairly well done. I saw same mistakes as in A3: people forget that M may
loop. Some provide uncomputable f by defining a TM for computing that
first runs M on w! Some mix reduction with proof by contradiction.
Some did not choose the right unrecognizable language to work with. Few
chose ETM-complement, which is recognizable! Most people know what has to
be shown, but fewer know how to show it (the details)!


Q3

 Give a detailed proof that the following language is NP-complete (your
proof will be marked on its structure as well as its content). In your
proof, you may use any of the known NP-complete problems listed at the
bottom of the last page (CLIQUE, HAMCYCLE, HAMPATH, 3SAT, VERTEXCOVER)

        L4 = {<G,k,h> / G is an undirected graph that contains both a
              clique of size k and an independent set of size h }

For example, the graph G =      /-------\  contains both a clique of size
                          a -- b -- c -- d
                           \-------/
3 ({a,b,c}) and an independent set of size 2 ({a,d}) but it does not
contain both a clique of size 3 and an independent set of size 3.

I. Showing L4 in NP

   A certificate for a "yes" instance <G,k,h> is c = (cc, ci), where
supposedly cc is a clique of size k, and ci, an indepedent set of size h.
We know both CLIQUE and IS are in NP, therefore we have polytime verifiers
Vc and Vi for them
Our verifier here is:

on input <G,k,h,cc,ci>
        run Vc on <G,k,cc>
        run Vi on <G,h,ci>
        and accept is both accept, otherwise reject

this is polytime because both Vc and Vi are
this works because Vc and Vi work

II. Showing L4 is NP-hard. We use a reduction from CLIQUE, that is known
to be NP-hard.

       To show CLIQUE <=p L4, map any <G,k> to <G, k, 1>
    Correctness: G has a clique of size k iff it has a clique of size k
and an independent set of size 1 (any graph has an independent set of size 1);
we assume non-empty graphs!

    This is poly time since we only do constant time work to add the "1"

I. and II. show L4 is NP-complete

8 p for strucure: 2 for "in NP", 2 for certificate+verifier, 2 for
NP-hard, 2 for reduction
4 p for good choice of known NP-hard problem
4 p for correct details, including 2 p for proof of correctness of
reduction

Pretty well done. Many people guessed CLIQUE and many gave a correct
reduction. Just one confuses the construction with the proof of
correctness of the reduction. Usual deductions where -2 for wrong
certificate or verifier, -2 for no or
incomplete proof, -1 for not mentioning poly time, or -4 for bad choice of
reduction.