CS 332: Elements of Theory of Computation Prof.
Boston University
December 10, 2021
Test 3 (Take-home part)
Copyright By PowCoder代写 加微信 powcoder
Read all the instructions on this page before beginning the exam.
Your solutions must be scanned and uploaded to Gradescope by 11:59PM Eastern Daylight Time,
Thursday, December 16, 2021.
Please prepare your solutions on your own paper as if you were completing a homework assign- ment. Both handwritten and typeset solutions are allowed. Make sure to clearly indicate which problem you are solving, both on your written solution and when you submit to Gradescope.
This exam contains 3 problems with multiple parts. The test is worth 75 points. There is also a bonus problem that will be accounted for in the usual way.
The exam is open-book in that you may freely consult the Sipser textbook, lecture notes and videos posted online, past homework assignments and solutions, discussion worksheets, your own class notes, and discussions on Piazza. You may not use any outside resources beyond those listed here.
You must complete the exam by yourself. No collaboration with anyone is permitted.
You do not need to spend time and paper rederiving facts that we have studied. You may cite known results and examples which were stated in lecture or proved in the main body of the text. This does not include homework problems, discussion section problems, or the solved exercises/problems in the text. You are, of course, free to use such results but you have to prove them first.
You will be graded not only on the correctness of your answer, but also on the clarity with which you express it. Make your writing large and neat.
If you need to ask a clarification question about one of the problems, please do so in an instructor- only post on Piazza. If the course staff believes your question may be a common one, we will change the settings of your post to be public to the class, keeping your identity anonymous.
Good luck! We hope you have fun solving these problems.
Problem 1 (Build-a-Language Workshop, 24 points). Identify a language satisfying each of the requested conditions, or assert that no such language can exist. Justify your answer in two or three sentences. No points will be given even for a correct answer if no justification is presented.
(a) A is in P, but A is not Turing-recognizable. (b) BisinNP,butBisnotinEXP.
(c) C ≤m ATM, and C is decidable.
(d) D is in NP, but D is not recognized by an NFA.
Problem 2 (Small TM, 24 points).
(a) Prove that if a TM M has exactly two states, then either L(M) = ∅ or L(M) = Σ∗.
(b) LetSMALLTM ={⟨M,s⟩|M isaTM,sisanaturalnumberandthereexistsans-stateTM N such that L(N) = L(M)}. Use a mapping reduction to prove that SMALLTM is not Turing-recognizable.
Problem 3 (Popular Cliques, 26 points). A popular clique in an undirected graph G = (V, E) is a set of vertices S such that a) S is a clique, i.e., all vertices in S are adjacent to each other and b) for every vertex v ∈ V , there exists a vertex w ∈ S such that v is adjacent to w. In the parlance of high school social dynamics, a popular clique is a group of students who are all friends with each other, and for which every student in the school is friends with at least one member of the clique.
DefinethelanguagePC={⟨G,k⟩| undirectedgraphG=(V,E)containsapopularcliquewith at least k vertices}.
(a) Show that PC ∈ NP. Describe your algorithm or verifier, explain why it is correct, and analyze its runtime.
(b) Show that PC is NP-hard (and hence NP-complete). Describe your reduction, explain why it is correct, and analyze its runtime.
Problem 4 (Bonus Problem). Two CNF formulas φ(x1, . . . , xn) and ψ(x1, . . . , xn) are equivalent if, for every assignment c ∈ {0, 1}n to the variables, φ(c) = ψ(c). The size of a CNF is the total number of literals appearing the formula counted with multiplicity. Show that if P = NP, then there is a polynomial-time algorithm that solves the following computational problem: Given a CNF formula φ(x1,…,xn), find an equivalent CNF formula ψ(x1,…,xn) that is the smallest possible, in the sense that every equivalent CNF requires has size greater or equal to ψ. (The width, i.e., number of disjunctions in each CNF clause does not matter.)
What makes this problem interesting is that neither the decision version of this problem, nor its complement, are believed to be in NP.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com