Questions and Answers of Introduction theory computation

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 Σ
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
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,
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
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
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
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
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
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.
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 =
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
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
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
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
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 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
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
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
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, .
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
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
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
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))]
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
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
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
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
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〉|
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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

Showing 100 - 200 of 388