Introduction to the theory of computation 3rd edition Michael Sipser - Solutions

Show that the following problem is NP-complete. You are given a set of states Q = {q0, q1, . . . , ql} and a collection of pairs {(s1, r1), . . . , (sk, rk)} where the si are distinct strings over Σ = {0, 1}, and the ri are (not necessarily distinct) members of Q. Determine whether a DFA M = (Q,
A subset of the nodes of a graph G is a dominating set if every other node of G is adjacent to some node in the subset. LetDOMINATING-SET = {〈G, k〉| G has a dominating set with k nodes}.Show that it is NP-complete by giving a reduction from VERTEX-COVER.
Recall, in our discussion of the Church–Turing thesis, that we introduced the language D = {〈p〉| p is a polynomial in several variables having an integral root}. We stated, but didn’t prove, that D is undecidable. In this problem, you are to prove a different property of D—namely, that D
In the following solitaire game, you are given an m × m board. On each of its m2 positions lies either a blue stone, a red stone, or nothing at all. You play by removing stones from the board until each column contains only stones of a single color and each row contains at least one stone. You win
This problem is inspired by the single-player game Minesweeper, generalized to an arbitrary graph. Let G be an undirected graph, where each node either contains a single, hidden mine or is empty. The player chooses nodes, one by one. If the player chooses a node containing a mine, the player loses.
Consider the following scheduling problem. You are given a list of final exams F1, . . . , Fk to be scheduled, and a list of students S1, . . . , Sl. Each student is taking some specified subset of these exams. You must schedule these exams into slots so that no student is required to take two
Let SET-SPLITTING = {〈S,C〉| S is a finite set and C = {C1, . . . ,Ck} is a collection of subsets of S, for some k > 0, such that elements of S can be colored red or blue so that no Ci has all its elements colored with the same color}. Show that SET-SPLITTING is NP-complete.
A coloring of a graph is an assignment of colors to its nodes so that no two adjacent nodes are assigned the same color. Let 3COLOR = {〈G〉| G is colorable with 3 colors}.Show that 3COLOR is NP-complete. Use the following three subgraphs. F T palette variable OR-gadget
You are given a box and a collection of cards as indicated in the following figure. Because of the pegs in the box and the notches in the cards, each card will fit in the box in either of two ways. Each card contains two columns of holes, some of which may not be punched out. The puzzle is solved
A cut in an undirected graph is a separation of the vertices V into two disjoint subsets S and T. The size of a cut is the number of edges that have one endpoint in S and the other in T. LetMAX-CUT = {〈G, k〉| G has a cut of size k or more}.Show that MAX-CUT is NP-complete. You may assume the
Let ϕ be a 3cnf-formula. An ≠-assignment to the variables of ϕ is one where each clause contains two literals with unequal truth values. In other words, an ≠-assignment satisfies ϕ without assigning three true literals in any clause.a. Show that the negation of any ≠-assignment to ϕ is
Let CNFH = {〈ϕ〉| ϕ is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal}. Show that CNFH ∈ P.
Let CNFk = {〈ϕ〉| ϕ is a satisfiable cnf-formula where each variable appears in at most k places}.a. Show that CNF2 ∈ P.b. Show that CNF3 is NP-complete.
Let HALF-CLIQUE = {〈G〉| G is an undirected graph having a complete subgraph with at least m/2 nodes, where m is the number of nodes in G}. Show that HALF-CLIQUE is NP-complete.
Let DOUBLE-SAT = {〈ϕ〉| ϕ has at least two satisfying assignments}. Show that DOUBLE SAT is NP-complete.
Let G represent an undirected graph. Also let SPATH = {〈G, a, b, k〉| G contains a simple path of length at most k from a to b}, And LPATH = {〈G, a, b, k〉| G contains a simple path of length at least k from a to b}.a. Show that SPATH ∈ P.b. Show that LPATH is NP-complete.
We generally believe that PATH is not NP-complete. Explain the reason behind this belief. Show that proving PATH is not NP-complete would prove P ≠ NP.
Show that PRIMES = {m| m is a prime number in binary} ∈ NP. For p > 1, the multiplicative group Z*p = {x| x is relatively prime to p and 1 ≤ x < p} is both cyclic and of order p − 1 if f p is prime. You may use this fact without justifying it. The stronger statement PRIMES ∈ P is now
Show that if P = NP, then every language A ∈ P, except A = ⌀ and A = Σ*, is NP-complete.
Let UNARY-SSUM be the subset sum problem in which all numbers are represented in unary. Why does the NP-completeness proof for SUBSET-SUM fail to show UNARY-SSUM is NP complete? Show that UNARY-SSUM ∈ P.
Show that NP is closed under the star operation.
Show that P is closed under the star operation. Use dynamic programming. On input y = y1 · · · yn for yi ∈ Σ, build a table indicating for each i ≤ j whether the substring yi · · · yj ∈ A* for any A ∈ P.)
A permutation on the set {1, . . . , k} is a one-to-one, onto function on this set. When p is a permutation, pt means the composition of p with itself t times. LetShow that PERM-POWER ∈ P. Note that the most obvious algorithm doesn’t run within polynomial time. First try it where t is a power
LetShow that MODEXP ∈ P. (Note that the most obvious algorithm doesn’t run in polynomial time. Try it first where b is a power of 2. MODEXP = {(a, b, c, p)| a, b, c, and p are positive binary integers such that a =c (mod p)}.
Call graphs G and H isomorphic if the nodes of G may be reordered so that it is identical to H. Let ISO = {〈G,H〉| G and H are isomorphic graphs}. Show that ISO ∈ NP.
In both parts, provide an analysis of the time complexity of your algorithm.a. Show that EQDFA ∈ P.b. Say that a language A is star-closed if A = A*. Give a polynomial time algorithm to test whether a DFA recognizes a star-closed language. (Note that EQNFA is not known to be in P.)
Show that ALLDFA is in P.
A triangle in an undirected graph is a 3-clique. Show that TRIANGLE ∈ P, where TRIANGLE = {〈G〉| G contains a triangle}.
Let CONNECTED = {〈G〉| G is a connected undirected graph}. Analyze the algorithm given on page 185 to show that this language is in P.
Show that NP is closed under union and concatenation.
Show that P is closed under union, concatenation, and complement.
Is the following formula satisfiable? (r V y) A (x Vy) ^ (EV y) A (E V g)
Fill out the table described in the polynomial time algorithm for context-free language recognition from Theorem 7.16 for string w = baba and CFG G:S → RTR → TR | aT → TR | b
Which of the following pairs of numbers are relatively prime? Show the calculations that led to your conclusions.a. 1274 and 10505b. 7289 and 8029
Answer each part TRUE or FALSE.a. n = o(2n).b. 2n = o(n2).Ac. 2n = o(3n).Ad. 1 = o(n).e. n = o(log n).f. 1 = o(1/n).
Answer each part TRUE or FALSE.a. 2n = O(n).b. n2 = O(n).Ac. n2 = O(n log2 n).Ad. n log n = O(n2).e. 3n = 2O(n).f. 22n = O(22n).
Let R ⊆ Nk be a k-ary relation. Say that R is definable in Th(N,+) if we can give a formula ‑ with k free variables x1, . . . , xk such that for all a1, . . . , ak ∈ N, ‑(a1, . . . , ak) is true exactly when a1, . . . , ak ∈ R. Show that each of the following relations
Let S = {〈M〉| M is a TM and L(M) = {〈M〉} }. Show that neither S nor S is Turing-recognizable.
Show that for any c, some strings x and y exist, where K(xy) > K(x)+K(y)+ c.
Show that the set of incompressible strings contains no infinite subset that is Turing-recognizable.
Show that the set of incompressible strings is undecidable.
Show that the function K(x) is not a computable function.
Use the result of Problem 6.21 to give a function f that is computable with an oracle for ATM, where for each n, f(n) is an incompressible string of length n.Problem 6.21Show how to compute the descriptive complexity of strings K(x) with an oracle for ATM.
Show how to compute the descriptive complexity of strings K(x) with an oracle for ATM.
Recall the Post Correspondence Problem that we defined in Section 5.2 and its associated language PCP. Show that PCP is decidable relative to ATM.
In Corollary 4.18, we showed that the set of all languages is uncountable. Use this result to prove that languages exist that are not recognizable by an oracle Turing machine with an oracle for ATM.
Show that E̅Q̅TM is recognizable by a Turing machine with an oracle for ATM.
Let A and B be two disjoint languages. Say that language C separates A and B if A ⊆ C and B ⊆ C. Describe two disjoint Turing-recognizable languages that aren’t separable by any decidable language.
Prove that there exist two languages A and B that are Turing-incomparable—that is, where A ≰T B and B ≰T A.
Show that for any language A, a language B exists, where A ≤T B and B ≰T A.
Show that for any two languages A and B, a language J exists, where A ≤T J and B ≤T J.
For each m > 1 let Zm = {0, 1, 2, . . . ,m − 1}, and let Fm = (Zm,+,×) be the model whose universe is Zm and that has relations corresponding to the + and × relations computed modulo m. Show that for each m, the theory Th(Fm) is decidable.
Let (N,<) be the model with universe N and the “less than” relation. Show that Th(N,<) is decidable.
Let ⌀eq be defined as in Problem 6.10. Give a model of the sentenceProblem 6.10.Give a model of the sentence Фед A Vx,y [R1 (x, y) → -R2(x, y) A Vx,y [¬R1 (x, y) → (R2(x, y) R2(y, x))] A Vz,y,z [(R2(x, y) ^ R2(y, 2)) → R2(x, z)] A Vx3y [R2(x,y)].
Give a model of the sentence Væ [R1(x, x)] A Ve,y[R1 (x, y) ++ R1(y, x)] A Va.y,z[(R1(2, y) A R1 (y, 2)) → R1 (x, z)]. Peg
Use the recursion theorem to give an alternative proof of Rice’s theorem in Problem 5.28.Problem 5.28.Let P be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turingmachine’s language has property P is undecidable.In more formal
Show that EQTM 6 ≰m E̅Q̅TM.
In the fixed-point version of the recursion theorem (Theorem 6.8), let the transformation t be a function that interchanges the states qaccept and qreject in Turing machine descriptions. Give an example of a fixed point for t.
Describe two different Turing machines, M and N, where M outputs 〈N〉 and N outputs 〈M〉, when started on any input.
Is the statement ∃x ∀ y [x+y=y] a member of Th(N,+)? Why or why not? What about the statement ∃x ∀ y [x+y=y]?
Let ATM' = {〈M,w〉| M is an oracle TM and MATM accepts w}. Show that ATM' is undecidable relative to ATM.
Show that if A ≤T B and B ≤T C, then A ≤T C.
Show that any infinite subset of MINTM is not Turing-recognizable.
Give an example in the spirit of the recursion theorem of a program in a real programming language (or a reasonable approximation thereof ) that prints itself out.
Let X = {〈M,w〉| M is a single-tape TM that never modifies the portion of the tape that contains the input w}. Is X decidable? Prove your answer.
Consider the problem of determining whether a PDA accepts some string of the form {ww| w ∈ {0,1}*} . Use the computation history method to show that this problem is undecidable.
Prove that the following two languages are undecidable.a. OVERLAPCFG = {〈G,H〉| G and H are CFGs where L(G) ∩ L(H) ≠ ⌀}.Adapt the hint in Problem 5.21.b. PREFIX-FREECFG = {〈G〉| G is a CFG where L(G) is prefix-free}.Problem 5.21.Let AMBIGCFG = {〈G〉| G is an ambiguous CFG}. Show
Let for any natural number x. If you start with an integer x and iterate f, you obtain a sequence, x, f(x), f(f(x)), . . . . Stop if you ever hit 1. For example, if x = 17, you get the sequence 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Extensive computer tests have shown that every
Use Rice’s theorem, which appears in Problem 5.28, to prove the undecidability of each of the following languages.Aa. INFINITETM = {〈M〉| M is a TM and L(M) is an infinite language}.b. {〈M〉| M is a TM and 1011 ∈ L(M)}.c. ALLTM = {〈M〉| M is a TM and L(M) = Σ*}.Problem
Show that both conditions in Problem 5.28 are necessary for proving that P is undecidable.Problem 5.28Let P be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turingmachine’s language has property P is undecidable.In more formal
Let P be any nontrivial property of the language of a Turing machine. Prove that the problem of determining whether a given Turingmachine’s language has property P is undecidable.In more formal terms, let P be a language consisting of Turing machine descriptions where P fulfills two conditions.
A two-dimensional finite automaton (2DIM-DFA) is defined as follows. The input is an m × n rectangle, for any m, n ≥ 2. The squares along the boundary of the rectangle contain the symbol # and the internal squares contain symbols over the input alphabet Σ. The transition function δ : Q × (Σ
Define a two-headed finite automaton (2DFA) to be a deterministic finite automaton that has two read-only, bidirectional heads that start at the left-hand end of the input tape and can be independently controlled to move in either direction. The tape of a 2DFA is finite and is just large enough to
Give an example of an undecidable language B, where B ≤m B.
Let J = {w| either w = 0x for some x ∈ ATM, or w = 1y for some y ∈ ATM }. Show that neither J nor J̅ is Turing-recognizable.
Show that A is decidable iff A ≤m 0*1*.
Show that A is Turing-recognizable iff A ≤m ATM.
Let AMBIGCFG = {〈G〉| G is an ambiguous CFG}. Show that AMBIGCFG is undecidable. Use a reduction from PCP. Given an instance of the Post Correspondence Problem, construct a CFG G with the ruleswhere a1, . . . , ak are new terminal symbols. Prove that this reduction works. S - T|B T +
Prove that there exists an undecidable subset of {1}*.
In the silly Post Correspondence Problem, SPCP, the top string in each pair has the same length as the bottom string. Show that the SPCP is decidable.
Show that the Post Correspondence Problem is undecidable over the binary alphabet Σ = {0,1}.
Show that the Post Correspondence Problem is decidable over the unary alphabet Σ = {1}.
Let Γ = {0, 1, ⊔} be the tape alphabet for all TMs in this problem. Define the busy beaver function BB: N → N as follows. For each value of k, consider all k-state TMs that halt when started with a blank tape. Let BB(k) be the maximum number of 1s that remain on the tape among all of these
Consider the problem of determining whether a Turing machine M on an input w ever attempts to move its head left at any point during its computation on w. Formulate this problem as a language and show that it is decidable.
Consider the problem of determining whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left most tape cell. Formulate this problem as a language and show that it is undecidable.
A useless state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any useless states. Formulate this problem as a language and show that it is undecidable.
Consider the problem of determining whether a single-tape Turing machine ever writes a blank symbol over a nonblank symbol during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Formulate this problem as a language and show that it is undecidable.
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape when it is run on input w. Formulate this problem as a language and show that it is undecidable.
Let T = {〈M〉| M is a TM that accepts wR whenever it accepts w}. Show that T is undecidable.
In the proof of Theorem 5.15, we modified the Turing machine M so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to M. Modify the PCP construction to handle this case.
Show that if A̅ is Turing-recognizable and A ≤m A̅, then A is decidable.
Show that ≤m is a transitive relation.
Show that ATM is not mapping reducible to ETM. In other words, show that no computable function reduces ATM to ETM. Use a proof by contradiction, and facts you already know about ATM and ETM.
If A ≤ m B and B is a regular language, does that imply that A is a regular language? Why or why not?
Find a match in the following instance of the Post Correspondence Problem. b a
Show that EQCFG is co-Turing-recognizable.
Show that EQCFG is undecidable.
The proof of Lemma 2.41 says that (q, x) is a looping situation for a DPDA P if when P is started in state q with x ∈ Γ on the top of the stack, it never pops anything below x and it never reads an input symbol. Show that F is decidable, where F = {〈P, q, x〉| (q, x) is a looping situation
Say that a variable A in CFL G is usable if it appears in some derivation of some string w ∈ G. Given a CFG G and a variable A, consider the problem of testing whether A is usable. Formulate this problem as a language and show that it is decidable.

Showing 100 - 200 of 388

Introduction to the theory of computation 3rd edition Michael Sipser - Solutions

Step by Step Answers