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 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 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 = { / 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 is not a TM or L(M)<>{00,11} } To show ATM <=m L3-complement: define f: S* -> S* by f(, 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 in ATM iff in L3-complement in ATM => M accepts w => M' accepts every x => L(M')=S*<>{00,11} => M' in L3-complement 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 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 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 run Vc on run Vi on 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 to 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.