UVa - cs302: Theory of Computation Spring 2008Problem Set 6 - ComplexityDue: Thursday, 24 April (2:02pm)This problem set focuses on material on computational complexity from Classes21-24 and Sipser’s book Chapter 7. Answer all 7 questions. For full credit, answersmust be concise, clear, and convincing, not just correct. Please staple your answersheets before class.Honor Policy (same as PS5). As with previous problem sets, you may discussand work on the problems with anyone you want. After your discussions, youmust destroy any notes from the meetings and write up your own solutions basedon your own understanding. This policy also applies to notes from problem-solving sessions that pertain to questions on the problem sets. You may preservenotes from these meetings that pertain to other problems or general questions, butshould not use notes from these meetings that include answers to specific ques-tions from the problem set.Problem 1: Asymptotic Notation. The way we advocated using asymptotic nota-tion to describe algorithm complexity in Classes 21 and 22 is different from howSipser uses it in Section 7.1. Describe (at least) two ways in which the book’s usediffers from the recommended use in class, and illustrate each with a specific ex-ample from Sipser’s text.Problem 2: Algorithm Analysis. What is the asymptotic run time of a Turingmachine that can decide this language from Exam 2, A = 0n1m0n/mwhere n ≥ 0and m ≥ 1 (that is, the input is n zeros, followed by m ones, followed by n dividedby m zeros)? A reasonable big-O bound with a convincing argument is worth fullcredit. A correct Θ bound for the stated problem (that is, an argument that there isno asymptotically faster algorithm exists) is worth bonus points, but be aware thatan incorrect Θ bound is worse than a correct big-O bound.Problem 3: Cyclical Turing Machines. Describe a problem for which a cyclicalTuring Machine (as defined in Problem 2b of Exam 2) can solve asymptoticallyfaster than it can be solved on a regular Turing Machine. The problem does notneed to be an interesting problem, but your answer should include a clear andconvincing argument, and explain why the problem is in TIME(t(n)) for the cycli-cal Turing Machine by not in the same time complexity class for the regular TM.Problem 4: Multidimensional Turing Machines. Sipser’s Theorem 7.8 shows thatfor every t(n) time multitape Turing machine there is an equivalent single-tapePS5-1Turing machine that has time in O(t2(n)). Consider the similar question for a t(n)time multi-dimensional Turing machine (as defined in Class 15). A correct prooffor any polynomial bound is worth full credit. If you can prove that your bound isthe lowest possible bound is worth at least 50 bonus points.Problem 5: Unary Subset Sum. (Sipser’s 7.16) Let UNARY SSUM be the subsetsum problem in which all numbers are represented in unary.a. Why does the NP-completeness proof for SUBSET SUM fail to showUNARY SSUM is NP-complete?b. Show that UNARY SSU M ∈ P.Problem 6: Genome Assembly. In order to assemble a genome, it is necessaryto combine snippets from many reads into a single sequence. The input is a setof n genome snippets, each of which is a string of up to k symbols. The outputis the smallest single string that contains all of the input snippets as substrings.For example, if the input is {ACCAGAATACC, TCCAGAATAA, TACCCGTGATCCA}, theoutput should be ACCAGAATACCCGTGATCCAGAATAA:ACCAGAATACCTCCAGAATAATACCCGTGATCCAa. Prove that the genome assembly problem is in NP.b. Prove that the genome assembly problem is NP-Complete.c. Explain how the human genome was sequenced even though it involvessolving an NP-Complete problem for a large input size. The human genomeis about 3 Billion base pairs. Readers at the time were able to read about700 bases per read fragment, and sequencing the genome involved aligningabout 30 million fragments.Problem 7: Complexity Congress. Write a short (no more than one page) essay ex-plaining the P = NP question in a way that (1) would be understandable to a typicalcongressperson, and (2) that makes it clear why it is a compelling and interestingproblem. Especially good answers will also convince the prospective congressper-son why it matters to them. Note that unlike some fifth graders, most congress-people (with the possible exceptions of Representatives Vern Ehlers, Bill Foster,Rush Holt, Jerry McNerney, and John Olver) should not be expected to alreadyunderstand what Turing Machines, algorithms, complexity classes, polynomials,and nondeterminism are, among other