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

Discover comprehensive support for "Introduction to the Theory of Computation, 3rd Edition" by Michael Sipser with our collection of expertly crafted resources. Access an online answers key and solutions manual to aid your understanding. Dive into solutions pdfs for solved problems, and explore questions and answers that enhance your grasp of the material. Benefit from our test bank and chapter solutions, offering step-by-step answers for thorough learning. Utilize the instructor manual and textbook resources to ensure a robust comprehension. All materials are available for free download, providing valuable assistance in mastering this essential subject.

Let CNFH = {〈ϕ〉| ϕ is a satisfiable cnf-formula where each clause contains any number of literals, but at most one negated literal}. Problem 7.25 asked you to show that CNFH ∈ P. Now give a log-space reduction from CIRCUIT-VALUE to CNFH to conclude that CNFH is P complete.Problem
Let BPL be the collection of languages that are decided by probabilistic log space Turing machines with error probability 1/3. Prove that BPL ⊆ P.
Let EQBP = {〈B1,B2〉| B1 and B2 are equivalent branching programs}. Show that EQBP is coNP complete.
Define a ZPP-machine to be a probabilistic Turing machine that is permitted three types of output on each of its branches: accept, reject, and ?. A ZPP-machine M decides a language A if M outputs the correct answer on every input string w (accept if w ∈ A and reject if w ∉ A) with probability
Show that if NP ⊆ BPP, then NP = RP.
Prove that if A is a regular language, a family of branching programs (B1,B2, . . .) exists wherein each Bn accepts exactly the strings in A of length n and is bounded in size by a constant times n.
Prove that if A is a language in L, a family of branching programs (B1,B2, . . .) exists wherein each Bn accepts exactly the strings in A of length n and is bounded in size by a polynomial in n.
Prove that for any integer p > 1, if p isn’t pseudoprime, then p fails the Fermat test for at least half of all numbers in Z+p .
Prove Fermat’s little theorem, which is given in Theorem 10.6. Consider the sequence a1, a2, . . . . What must happen, and how?
Recall that NPSAT is the class of languages that are decided by nondeterministic polynomial time Turing machines with an oracle for the satisfiability problem. Show that NPSAT = Σ2P.
Show that if PH = PSPACE, then the polynomial time hierarchy has only finitely many distinct levels.
Show that if P = NP, then P = PH.
LetM be a probabilistic polynomial time Turing machine, and let C be a language where for some fixed 0 < ε1 < ε2 < 1,a. w ∉ C implies Pr[M accepts w] ≤ ε 1, andb. w ∈ C implies Pr[M accepts w] ≥ ε2.Show that C ∈ BPP. Use the result of Lemma 10.5.
A k-head pushdown automaton (k-PDA) is a deterministic pushdown automaton with k read only, two-way input heads and a read/write stack. Define the class PDAk = {A| A is recognized by a k-PDA}. Show that P = S ∪k PDAk. Recall that P equals alternating log space.
A Boolean formula is a Boolean circuit wherein every gate has only one output wire. The same input variable may appear in multiple places of a Boolean formula. Prove that a language has a polynomial size family of formulas iff it is in NC1. Ignore uniformity considerations.
Let A be a regular language over {0,1}. Show that A has size–depth complexity (O(n),O(log n)).
Show that BPP ⊆ PSPACE.
Show that any function with n inputs can be computed by a branching program that has O(2n) nodes.
Show that the majority function with n inputs can be computed by a branching program that has O(n2) nodes.
Show that the parity function with n inputs can be computed by a branching program that has O(n) nodes.
Prove that if A ≤L B and B is in NC, then A is in NC.
Show that 12 is not pseudoprime because it fails some Fermat test.
Show that a circuit family with depth O(log n) is also a polynomial size circuit family.
Define the function majorityn as in Problem 9.24. Show that it may be computed with O(n) size circuits.Problem 9.24.Recall that you may consider circuits that output strings over {0,1} by designating several output gates. Let addn : {0,1}2n → {0,1}n+1 take two n bit binary integers and produce
Define the function majorityn : {0,1}n → {0,1} as Thus, the majorityn function returns the majority vote of the inputs. Show that majorityn can be computed with:a. O(n2) size circuits.b. O(n log n) size circuits. Recursively divide the number of inputs in half and use the result of Problem
Recall that you may consider circuits that output strings over {0,1} by designating several output gates. Let addn : {0,1}2n → {0,1}n+1 take two n bit binary integers and produce the n+1 bit sum. Show that you can compute the addn function with O(n) size circuits.
Suppose that A and B are two oracles. One of them is an oracle for TQBF, but you don’t know which. Give an algorithm that has access to both A and B, and that is guaranteed to solve TQBF in polynomial time.
A k-query oracle Turing machine is an oracle Turing machine that is permitted to make at most k queries on each input. A k-query oracle Turing machine M with an oracle for A is written MA,k. Define PA,k to be the collection of languages that are decidable by polynomial time k-query oracle Turing
Prove that an oracle C exists for which NPC ≠ coNPC.
Define the unique-sat problem to beUSAT = {〈ϕ〉| ϕ is a Boolean formula that has a single satisfying assignment}. Show that USAT ∈ PSAT.
Let EREX" = {〈R〉| R is a regular expression with exponentiation and L(R) = ⌀}. Show that EREX↑ ∈ P.
Read the definition of a 2DFA (two-headed finite automaton) given in Problem 5.26. Prove that P contains a language that is not recognizable by a 2DFA.Problem 5.26.Define a two-headed finite automaton (2DFA) to be a deterministic finite automaton that has two read-only, bidirectional heads that
Prove that TQBF ∉ SPACE(n1/3).
Define pad as in Problem 9.13.a. Prove that for every A and natural number k, A ∈ P iff pad(A, nk) ∈ P.b. Prove that P ≠ SPACE(n).Problem 9.13Consider the function pad : Σ* × N → Σ*#* that is defined as follows. Let pad(s, l) = s#j , where j = max(0, l−m) andm is
Prove that if NEXPTIME ≠ EXPTIME, then P ≠ NP. You may find the function pad, defined in Problem 9.13, to be helpful.Problem 9.13Consider the function pad : Σ* × N → Σ*#* that is defined as follows. Let pad(s, l) = s#j , where j = max(0, l−m) andm is the length of s. Thus, pad(s, l)
Consider the function pad : Σ* × N → Σ*#* that is defined as follows. Let pad(s, l) = s#j , where j = max(0, l−m) andm is the length of s. Thus, pad(s, l) simply adds enough copies of the new symbol # to the end of s so that the length of the result is at least l. For any language A and
Describe the error in the following fallacious “proof” that P ≠ NP. Assume that P = NP and obtain a contradiction. If P = NP, then SAT ∈ P and so for some k, SAT ∈ TIME(nk). Because every language in NP is polynomial time reducible to SAT, you have
Show that the language MAX-CLIQUE from Problem 7.48 is in PSAT.Problem 7.48The difference hierarchy DiP is defined recursively asa. D1P = NP andb. DiP = {A| A = B \ C for B in NP and C in Di−1P}.(Here B \ C = B ∩ C.)For example, a language in D2P is the difference of two NP languages. Sometimes
Problem 8.13 showed that ALBA is PSPACE-complete.a. Do we know whether ALBA ∈ NL? Explain your answer.b. Do we know whether ALBA ∈ P? Explain your answer.Problem 8.13Show that TQBF restricted to formulas where the part following the quantifiers is in conjunctive normal form is still
Show that if NP = PSAT, then NP = coNP.
If R is a regular expression, let R{m,n} represent the expressionRm ∪ Rm+1 ∪ · · · ∪ Rn.Show how to implement the R{m,n} operator, using the ordinary exponentiation operator, but without “· · · ”.
Give regular expressions with exponentiation that generate the following languages over the alphabet {0,1}.Aa. All strings of length 500Ab. All strings of length 500 or lessAc. All strings of length 500 or moreAd. All strings of length different than 500e. All strings that contain exactly 500 1sf.
Prove that if A ∈ P, then PA = P.
Give a circuit that computes the parity function on three input variables and show how it computes on input 011.
Show how the circuit depicted in Figure 9.26 computes on input 0110 by showing the values computed by all of the gates, as we did in Figure 9.24.Figure 9.26 Figure 9.24 13 12 V
Prove that NTIME(n) ⊆ PSPACE.
Prove that TIME(2n) ⊆ TIME(22n).
Prove that TIME(2n) = TIME(2n+1).
Define CYCLE = {〈G〉| G is a directed graph that contains a directed cycle}. Show that CYCLE is NL-complete.
Give an example of an NL-complete context-free language.
Let CNFH1 = {〈ϕ〉| ϕ is a satisfiable cnf-formula where each clause contains any number of positive literals and at most one negated literal. Furthermore, each negated literal has at most one occurrence in ϕ}. Show that CNFH1 is NLϕ complete.
Show that 2SAT is NL-complete.
Show that EDFA is NL-complete.
Show that ANFA is NL-complete.
Let BOTHNFA = {〈M1,M2〉|M1 and M2 are NFAs where L(M1)\L(M2) ≠ ;}. Show that BOTHNFA is NL-complete.
Recall that a directed graph is strongly connected if every two nodes are connected by a directed path in each direction. LetSTRONGLY-CONNECTED = {〈G〉| G is a strongly connected graph}.Show that STRONGLY-CONNECTED is NL-complete.
Define UPATH to be the counterpart of PATH for undirected graphs. Show that BIPARTITE ≤ L UPATH. (Note: In fact, we can prove UPATH ∈ L, and therefore BIPARTITE ∈ L, but the algorithm [62] is too difficult to present here.)
An undirected graph is bipartite if its nodes may be divided into two sets so that all edges go from a node in one set to a node in the other set. Show that a graph is bipartite if and only if it doesn’t contain a cycle that has an odd number of nodes. Let BIPARTITE = {〈G〉| G is a bipartite
For each n, exhibit two regular expressions, R and S, of length poly(n), where L(R) ≠ L(S), but where the first string on which they differ is exponentially long. In other words, L(R) and L(S) must be different, yet agree on all strings of length up to 2εn for some constant ε > 0.
Define UCYCLE = {〈G〉| G is an undirected graph that contains a simple cycle}. Show that UCYCLE ∈ L. (Note: G may be a graph that is not connected.)
a. Let ADD = {〈x, y, z〉| x, y, z > 0 are binary integers and x+ y = z}. Show that ADD ∈ L.b. Let PAL-ADD = {〈x, y〉| x, y > 0 are binary integers where x + y is an integer whose binary representation is a palindrome}. (Note that the binary representation of the sum is
For any positive integer x, let xR be the integer whose binary representation is the reverse of the binary representation of x. (Assume no leading 0s in the binary representation of x.) Define the function R+ : N−!N where R+(x) = x + xR.a. Let A2 = {〈x, y〉| R+(x) = y}. Show A2 ∈ L.b.
Let MULT = {a#b#c| a, b, c are binary natural numbers and a × b = c}. Show that MULT ∈ L.
The game of Nim is played with a collection of piles of sticks. In one move, a player may remove any nonzero number of sticks from a single pile. The players alternately take turns making moves. The player who removes the very last stick loses. Say that we have a game position in Nim with k piles
Let B be the language of properly nested parentheses and brackets. For example, ([()()]()[]) is in B but ([)] is not. Show that B is in L.
Let A be the language of properly nested parentheses. For example, (()) and (()(()))() are in A, but )( is not. Show that A is in L.
Consider the following two-person version of the language PUZZLE that was described in Problem 7.28. Each player starts with an ordered stack of puzzle cards. The players take turns placing the cards in order in the box and may choose which side faces up. Player I wins if all hole positions are
The cat-and-mouse game is played by two players, “Cat” and “Mouse,” on an arbitrary undirected graph. At a given point, each player occupies a node of the graph. The players take turns moving to a node adjacent to the one that they currently occupy. A special node of the graph is called
Define ALBA = {〈M,w〉| M is an LBA that accepts input w}. Show that ALBA is PSPACE complete.
Show that TQBF restricted to formulas where the part following the quantifiers is in conjunctive normal form is still PSPACE-complete.
Show that if every NP-hard language is also PSPACE-hard, then PSPACE = NP.
The Japanese game go-moku is played by two players, “X” and “O,” on a 19 × 19 grid. Players take turns placing markers, and the first player to achieve five of her markers consecutively in a row, column, or diagonal is the winner. Consider this game generalized to an n × n board.
Let LADDERDFA = {〈M, s, t〉| M is a DFA and L(M) contains a ladder of strings, starting with s and ending with t}. Show that LADDERDFA is in PSPACE.
A ladder is a sequence of strings s1, s2, . . . , sk, wherein every string differs from the preceding one by exactly one character. For example, the following is a ladder of English words, starting with “head” and ending with “free”: head, hear, near, fear, bear, beer, deer, deed, feed,
Let EQREX = {〈R, S〉| R and S are equivalent regular expressions}. Show that EQREX ∈ PSPACE.
Show that NL is closed under the operations union, concatenation, and star.
Show that any PSPACE-hard language is also NP-hard.
Show that ADFA ∈ L.
Show that PSPACE is closed under the operations union, complementation, and star.
Consider the following generalized geography game wherein the start node is the one with the arrow pointing in from nowhere. Does Player I have a winning strategy? Does Player II? Give reasons for your answers. (1 2 3 4 5 6.
Consider the following position in the standard tic-tac-toe game.Let’s say that it is the ×-player’s turn to move next. Describe a winning strategy for this player. (Recall that a winning strategy isn’t merely the best move to make in the current position. It also includes all the responses
Show that for any function f : N → R+, where f(n) ≥ n, the space complexity class SPACE(f(n)) is the same whether you define the class by using the singletape TM model or the two-tape read only input TM model.
In a directed graph, the indegree of a node is the number of incoming edges and the outdegree is the number of outgoing edges. Show that the following problem is NP-complete. Given an undirected graph G and a designated subset C of G’s nodes, is it possible to convert G to a directed graph by
Let A ⊆ 1* be any unary language. Show that if A is NP-complete, then P = NP. Consider a polynomial time reduction f from SAT to A. For a formula ϕ, let ϕ0100 be the reduced formula where variables x1, x2, x3, and x4 in ϕ are set to the values 0, 1, 0, and 0, respectively. What
Show that P is closed under homomorphism iff P = NP.
This problem investigates resolution, a method for proving the unsatisfiability of cnf-formulas. Let ‑ = C1 ∧ C2 ∧· · ·∧Cm be a formula in cnf, where the Ci are its clauses. Let C = {Ci| Ci is a clause of ϕ}. In a resolution step, we take two clauses Ca and Cb in C, which both have
Call a regular expression star-free if it does not contain any star operations. Then, let EQSF−REX = {〈R, S〉| R and S are equivalent star-free regular expressions}. Show that EQSF−REX is in coNP. Why does your argument fail for general regular expressions?
Let f : N → N be any function where f(n) = o(n log n). Show that TIME(f(n)) contains only the regular languages.
Let MAX-CLIQUE = {〈G, k〉| a largest clique in G is of size exactly k}. Use the result of Problem 7.47 to show that MAX-CLIQUE is DP-complete.
The difference hierarchy DiP is defined recursively asa. D1P = NP andb. DiP = {A| A = B \ C for B in NP and C in Di−1P}.(Here B \ C = B ∩ C.)For example, a language in D2P is the difference of two NP languages. Sometimes D2P is called DP (and may be written DP). Let Z = {〈G1, k1,G2, k2〉| G1
Say that two Boolean formulas are equivalent if they have the same set of variables and are true on the same set of assignments to those variables (i.e., they describe the same Boolean function). A Boolean formula is minimal if no shorter Boolean formula is equivalent to it. Let MIN FORMULA be the
Modify the algorithm for context-free language recognition in the proof of Theorem 7.16 to give a polynomial time algorithm that produces a parse tree for a string, given the string and a CFG, if that grammar generates the string.
A 2cnf-formula is an AND of clauses, where each clause is an OR of at most two literals. Let 2SAT = {〈ϕ〉| ϕ is a satisfiable 2cnf-formula}. Show that 2SAT ∈ P.
For a cnf-formula ‑ with m variables and c clauses, show that you can construct in polynomial time an NFA with O(cm) states that accepts all nonsatisfying assignments, represented as Boolean strings of length m. Conclude that P ≠ NP implies that NFAs cannot be minimized in polynomial time.
Consider the algorithm MINIMIZE, which takes a DFA M as input and outputs DFA M'. MINIMIZE = “On input hMi, whereM = (Q,Σ, δ, q0,A) is a DFA:1. Remove all states of M that are unreachable from the start state.2. Construct the following undirected graph G whose nodes are the states of M.3. Place
In the proof of the Cook–Levin theorem, a window is a 2 × 3 rectangle of cells. Show why the proof would have failed if we had used 2 × 2 windows instead.
Show that if P = NP, a polynomial time algorithm exists that takes an undirected graph as input and finds a largest clique contained in that graph. (See the note in Problem 7.38.)Problem 7.38.Show that if P = NP, a polynomial time algorithm exists that produces a satisfying assignment when given a
Show that if P = NP, you can factor integers in polynomial time. (See the note in Problem 7.38.)Problem 7.38.Show that if P = NP, a polynomial time algorithm exists that produces a satisfying assignment when given a satisfiable Boolean formula. Note: The algorithm you are asked to provide computes
Show that if P = NP, a polynomial time algorithm exists that produces a satisfying assignment when given a satisfiable Boolean formula. Note: The algorithm you are asked to provide computes a function; but NP contains languages, not functions. The P = NP assumption implies that SAT is in P, so
Let U = {〈M, x, #t〉| NTM M accepts x within t steps on at least one branch}. Note that M isn’t required to halt on all branches. Show that U is NP-complete.

Showing 1 - 100 of 388

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

Step by Step Answers