Questions and Answers of Introduction theory computation

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
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
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.
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
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
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
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
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.
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
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
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
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 : Σ*
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
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
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,
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 =
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
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
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
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
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
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
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
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
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
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