Course: CSC333, Automata, Computability and Computational Theory Exam-3: Complexity theory, NP-completeness, polynomial-time reducibility. STUDENT’s NAME: This exam is intended to be an individual eort. You are NOT allowed to use and reference the textbook, your homework assignments, your notes, the class slides, or other sources, such as your classmates and the internet at large. 1. Provide a solution to ALL problems for each question; there are total of 8 questions. 2. Good luck! 3. The Total Exam Score: out of (100 points) 4. : Some of the questions are multiple choice questions, choosing the wrong option will result in -1 point deduction for each wrong choice. Cheat Sheet: Proving NP??completeness via Reduction Step 1 (Verication): Show that Pnew is in NP Design a pseudo-code for verifying the solution for Pnew Prove that the verication procedure is polynomial in time Step 2 (Reduction): Show that Pnew is NP??hard (Part I) Identify a known NP-hard problem, Pknown Design a pseudo-code for reduction: Pknown ! Pnew Prove that the reduction procedure is polynomial in time Step 3 (Correctness): Show that Pnew is NP??hard (Part II) Claim that Pknown is decidable if and only if Pnew is decidable { Proof: Assume Pknown is decidable. Prove that Pnew is decidable { Proof: Assume Pnew is decidable. Prove that Pknown is decidable 1
1. out of (18 points), 6 points each: Let n be the number of vertices, m the number of edges, and d the maximum degree of some graph G. Choose the best upper or lower bound for each statement: (a) The maximum clique size of G is no larger than A. d B. n ?? d C. d + 1 D. n E. n=2 F. n ?? 1 (b) The maximum independent set size of G, the com- plement of G, is no larger than A. d B. n ?? d C. d + 1 D. n E. n=2 F. n ?? 1 (c) The minimum vertex cover size of G is no larger than A. d B. n ?? d C. d + 1 D. n E. n=2 F. n ?? 1 2
2. out of (12 points), 3 points each: Let n be the number of vertices and m the number of edges of some graph G. Let D be the…