Kozen D.C. Theory of Computation

Подождите немного. Документ загружается.

296 Miscellaneous Exercises

41. (a) Show that any deterministic logspace transducer can be simulated

by a family of NC circuits with multiple output wires.

(b) We showed in Theorem 6.1 that the circuit value problem (CVP) is

≤

log

-complete for P. Conclude from this and part (a) that CVP ∈

NC if and only if P = NC .

42. Consider the following Standard ML program to compute the greatest

common divisor (gcd) of two numbers m, n, not both of which are 0.

fun Euclid(m:int, n:int) : int * int * int =

ifn=0then (1,0,m)

else let

val q = m div n

val r = m mod n

val (s,t,g) = Euclid(n,r)

(t,s-t*q,g)

end

Here div computes the quotient and mod the remainder when dividing

m by n using ordinary integer division. Prove that the output of the

program is a triple (s, t, g), where g is the gcd of m and n and s, t are

integers such that sm + tn = g.

43. Let a and n be positive integers. Prove that the following are equivalent.

(i) a has an order modulo n; that is, there exists m such that a

≡

1(modn).

(ii) a is relatively prime to n;thatis,gcd(a, n)=1.

(iii) a is invertible modulo n; that is, there exists b,1≤ b ≤ n −1, such

that ab ≡ 1(modn).

44. Prove the following ampliﬁcation lemma for IP and PCP analogous

to Lemma 14.1 for BPP and RP.IfL has an IP (respectively, PCP)

protocol that uses r(n) random bits and makes q(n) queries, then for

any ε>0, L has an IP (respectively, PCP)protocol(P, V )thatuses

kr(n) random bits and makes kq(n) queries and has error probability

bounded by ε,wherek is O(−log ε). In the case of PCP, this means

(i) if x ∈ L then Pr((P, V ) accepts x)=1,

Miscellaneous Exercises 297

(ii) if x ∈ L then for any P



,Pr((P



,V) accepts x) ≤ ε,

and in the case of IP,

(i) if x ∈ L then Pr((P, V ) accepts x) ≥ 1 − ε,

(ii) if x ∈ L then for any P



,Pr((P



,V) accepts x) ≤ ε.

45. In this exercise we complete the proof of Lemma 18.2. Let B be a

Boolean formula in 3CNF with m clauses over n variables x

,... ,x

such that each clause contains exactly three literals with distinct vari-

ables. Let S

and S be as in the proof of Lemma 18.2. As argued in that

proof, E(S)=7m/8. Let a

,... ,a

∈{0, 1} be the truth assignment

to x

,... ,x

obtained from the greedy algorithm. For a random truth

assignment r

,... ,r

,letE

be the event

def



i=1

= a

Then E(S | E

k−1

∧ r

= a

) ≥ E(S | E

k−1

∧ r

= a

), because that was

how we chose a

in the greedy algorithm.

(a) Show how to calculate E(S | E

) eﬃciently.

(b) Prove that

E(S | E

k−1

)=E(S | E

k−1

∧ r

= a

) · Pr(r

= a

| E

k−1

)

+ E(S | E

k−1

∧ r

= a

) · Pr(r

= a

| E

k−1

) ≤ E(S | E

(d) Using (c), show that the greedy assignment a

,... ,a

satisﬁes at

least 7m/8clauses.

46. Show that if P = NP,then

(a) MAX-3SAT

(b) MAX-CLIQUE

can be solved exactly in polynomial time (see Lecture 18).

47. Complete the proof of Theorem 18.3 by proving the following claims

about the construction in that proof.

298 Miscellaneous Exercises

(a) Show that if a = b,then(y, a)and(y, b) are not consistent, thus

((y, a), (y, b)) cannot be an edge of the graph.

(b) Show that if x ∈ L, then the maximum clique of G is of size n

whereas if x ∈ L, the maximum clique of G is of size strictly less

than αn

48. Let F = Z

for some prime p.GiveaPCP(n

, 1) protocol for determining

for given oracles f : F

→ F and f : F

→ F whether f is close to a

function of the form r → r

•

a and h is close to a function of the form

t → t

•

(a ⊗ a ⊗ a)forsomea ∈ F

(see Lecture 20).

49. Come up with a deﬁnition of trivial for ﬁrst-order theories in terms of

constraints on the signature. Prove that for your deﬁnition of trivial,

(a) Every nontrivial theory is PSPACE -hard.

(b) Every trivial theory is decidable in polynomial time.

50. An Ehrenfeucht–Fraiss´e game is said to be ﬁnite if from each board

position, there are only ﬁnitely many legal next moves. Show that every

ﬁrst-order theory is characterized by a ﬁnite Ehrenfeucht–Fraiss´e game.

Why does this not show that every ﬁrst-order theory is decidable?

51. Prove that the set of sets of inﬁnite strings accepted by deterministic

B¨uchi automata is closed under union and intersection.

52. What is the complexity of the emptiness problem for nondeterministic

B¨uchi automata? Give proof.

53. How hard is it to determine whether a given

(a) deterministic

∗H

(b) nondeterministic

B¨uchi automaton accepts all strings? Give proof.

54. Show that every set accepted by a B¨uchi automaton is a ﬁnite union of

sets of the form AB

,whereA and B are regular sets. Here B

denotes

the set of inﬁnite words of the form w

···,wherew

∈ B −{ε} for

all i ≥ 0.

Miscellaneous Exercises 299

55. Prove that equicardinality of sets, that is, the predicate

ϕ(A, B)

def

⇐⇒ A and B have the same number of elements,

cannot be expressed in S1S.

56. Consider the following two acceptance conditions for automata on inﬁ-

nite words.

(a) Streett condition: As with the Rabin acceptance condition, there

is a ﬁnite set of pairs (G

), 1 ≤ i ≤ k,whereG

and R

are

subsets of Q.Arunσ is accepting if for all i,IO(σ) ∩ G

= ∅

implies IO(σ) ∩ R

= ∅.

(b) Parity condition: Assume that the states of the automaton are

numbered {0, 1,... ,n − 1}.Arunσ is accepting if the least-

numbered state that occurs inﬁnitely often is even.

Show that for nondeterministic automata, these two acceptance con-

ditions are equivalent to the other acceptance conditions discussed in

Lectures 25 and 26.

57.

(a) Prove that (1 − 1/z)

≤ e

−1

for all z>0 and that (1 − 1/z)

approaches e

−1

in the limit as z →∞,wheree =2.718 ... is the

base of natural logarithms.

(b) Prove that (1 + 1/z)

≤ e for all z>0 and that (1 + 1/z)

ap-

proaches e in the limit as z →∞.

58. Construct a recursive oracle A such that NP

=co-NP

59. (Cai and Ogihara [25]) In this exercise, we give an alternative proof of

Mahaney’s theorem (Theorem 29.2). Suppose that S is a sparse NP-hard

set. For a Boolean formula ϕ of length n and truth assignment t ∈{0, 1}

to the variables of ϕ,letϕ(t) denote the truth value obtained by evalu-

ating ϕ at t.Let≤

lex

denote lexicographic order on truth assignments

of the same length. Deﬁne the set

def

= {(ϕ, s) |∃ts≤

lex

t ∧ ϕ(t)=1}.

Observe that if (ϕ, t) ∈ E and s ≤

lex

t,then(ϕ, s) ∈ E.Wegivea

polynomial-time decision procedure for E.

300 Miscellaneous Exercises

(a) Show that E is NP-complete. Thus the existence of a polynomial-

time decision procedure for E implies P = NP.

(b) Let σ be a polynomial-time many–one reduction from E to S with

time bound n

. Show that there exists a polynomial n

such that

|S ∩ Σ

≤n

|≤n

Let ϕ beaBooleanformulaoflengthn.LetA

= {0, 1}

,thesetofall

truth assignments to the variables of ϕ. We construct a sequence of sub-

sets A

⊇ A

⊇··· of decreasing size, maintaining the following

invariant: if ϕ is satisﬁable, then A

contains a satisfying assignment.

Here is how we get A

i+1

from A

. Suppose A

= {t

,... ,t

m−1

}⊆

{0, 1}

,wheret

≤

lex

≤

lex

···≤

lex

m−1

,andm ≥ n

+ 1 (the d is

the same d as in part (b)). Let

def

= {km/(n

+1)|0 ≤ k ≤ n

}⊆{0, 1, 2,... ,m− 1}.

This is a set of n

+ 1 evenly spaced indices of elements of A

+1) < (k +1)m/(n

+1) for all k,thusJ

contains n

+ 1 distinct elements.

Compute σ(ϕ, t

)foreachj ∈ J. If there exist i, j ∈ J with i<jand

σ(ϕ, t

)=σ(ϕ, t

), remove the interval {t

| i ≤ k<j} from A

.Ifon

the other hand all σ(ϕ, t

) are distinct for j ∈ J, remove the last interval

| k ≥ n

m/(n

+1)} from A

(d) Argue that in either case, the invariant is maintained.

(e) In either case, we remove at least |A

|/(n

+ 1) elements from

. Using Miscellaneous Exercise 57(a), show that after at most

+1)(n ln 2 − ln(n

+1)) = O(n

d+1

) steps, we get down to a

small enough set that we can evaluate ϕ on all the remaining truth

assignments directly.

(f) The sets A

produced in this construction are of exponential size

in general. However, they can be represented eﬃciently so that the

above procedure can be carried out in polynomial time. Describe a

representation for the sets A

that allows |A

| and the maps j → t

to be calculated eﬃciently.

60. (a) Recall that a square matrix is nonsingular if all its columns are

linearly independent. Show there are exactly



n−1

i=0

− q

)non-

singular n × n matrices over GF

Miscellaneous Exercises 301

∗H

(b) Show how to generate a random n×n nonsingular matrix over GF

eﬃciently, all nonsingular matrices equally likely.

61. If E is a subspace of an n-dimensional vector space V , let dim E and

codim E denote the dimension and codimension (n minus the dimension)

of E, respectively. Show that codim E ∩ F ≤ codim E +codimF .

62. Prove that the lower bound 3/4 established in Lemma F.1 is tight for

all n.

63. (Papadimitriou and Zachos [93]) The class ⊕P (“parity P”) is deﬁned to

be the class of sets A for which there exists a polynomial-time nondeter-

ministic TM M such that x ∈ A iﬀ the number of accepting computation

paths of M on input x is odd. Equivalently, we can think of the machine

M as a kind of alternating machine that at branching nodes computes

the mod-2 sum of the labels of its children. Another characterization of

⊕P is given in Lecture G. Prove that ⊕P

⊕P

= ⊕P.

64. Show that the following two characterizations of #P are equivalent.

(a) A function f : {0, 1}

∗

→ N is in #P iﬀ there exist A ∈ P and

k ≥ 0 such that for all x, f(x)=|W (n

,A,x) |.

(b) A function f : {0, 1}

∗

→ N is in #P iﬀ there is a polynomial-

time nondeterministic TM M such that the number of accepting

computation paths of M on input x is f(x).

65. In the proof of Toda’s theorem (Theorem G.1), we need to know that

the polynomial h

(z) satisﬁes the property

z is odd ⇒ h

(z) ≡−1(mod2

)

z is even ⇒ h

(z) ≡ 0(mod2

where

h(z)

def

=4z

+3z

(z)

def

= z

m+1

(z)

def

= h(h

(z)).

Show that this is so.

302 Miscellaneous Exercises

66. Prove the following clauses of Lemma G.2. If C is closed downward under

≤

,then

(ii) Π

log

·⊕·C ⊆⊕·C;

∗HS

(iii) ⊕·BP ·C ⊆ BP ·⊕·C;

(iv) BP · BP · C ⊆ BP ·C;

(v) ⊕·⊕·C ⊆⊕·C;

(vi) BP ·C and ⊕·C are closed downward under ≤

67. Let #P denote the class of all polynomial-time counting functions. A

formal deﬁnition of this class is given in Lecture G. Show that #P is

closed under the following pointwise operations.

(a) Addition: if f,g ∈ #P,thensoisf + g = λx.f(x)+g(x).

(b) Multiplication: if f,g ∈ #P,thensoisf ·g = λx.f(x)g(x).

∗

|x |

for any constant d.

∗S

(d) Let g : {0, 1}

∗

→ N[z] be a function that on input x ∈{0, 1}

∗

gives a polynomial with indeterminate z and positive integer co-

eﬃcients representing a polynomial function N → N. Suppose g is

polynomial-time computable in the sense that g(x) is of degree at

most polynomial in |x|, the coeﬃcients of g(x) can be represented

in binary with at most polynomially many bits, and the coeﬃcient

of z

can be produced from x and i in polynomial time. Show that

if f is in #P,thensoisλx.g(x)(f(x)).

68. (Papadimitriou [92]) Some computations produce an output f(x)on

input x that is in the worst case much larger than |x|. For such problems,

we would like to have algorithms that are polynomial in |x|+ |f(x)| to

decide for a given x, y whether f(x)=y. The class of all such problems

is called output polynomial time.

(a) Consider the function that for a given regular expression pro-

duces the minimum-state equivalent deterministic ﬁnite automa-

ton. Prove that this function is in output polynomial time iﬀ

P = PSPACE.

Miscellaneous Exercises 303

(b) Prove that it is impossible to produce in output polynomial time

an equivalent deterministic automaton that has at most poly-

nomially more states than the minimum-state automaton unless

P = PSPACE.

69. (a) Prove that

(z ∧ u) ∨ (

z ∧ v) ≡ (z → u) ∧ (z → v).

(b) Let ψ(x) be any Boolean formula with a single positive occurrence

of the Boolean variable x along with possibly other variables. Here

positive means in the scope of an even number of negations. Show

that

ψ(x

∨ x

)=ψ(x

) ∨ ψ(x

)

ψ(x

∧ x

)=ψ(x

) ∧ ψ(x

where x

and x

do not occur in ψ(x).

oracle machine can be eﬃciently simulated by

another Σ

oracle machine that makes all its oracle queries at the

end of the computation.

70. Let excl(z,u, v) denote the Boolean formula on the left-hand side of the

equation in Exercise 69(a) (or the equivalent formula on the right-hand

side). Let ϕ(x) be any Boolean formula with Boolean variable x and

possibly other variables. Prove that

ϕ(excl(z,u, v)) ≡ excl(z,ϕ(u),ϕ(v)).

71. A minterm of a Boolean formula ϕ is a ≤-maximal term M such that

M ≤ ϕ.Ifϕ is a CNF formula, show that M is a minterm of ϕ iﬀ M

contains at least one literal from each clause of ϕ and no proper subterm

of M has this property.

72. Let ϕ be a Boolean formula. Show that the disjunction of all minterms

of ϕ isaDNFformulaequivalenttoϕ.

73. Prove that if the G

are mutually exclusive events that cover F ,then

Pr(E | F )=



Pr(E | G

∧ F ) · Pr(G

| F )

≤ max

Pr(E | G

∧F ).

304 Miscellaneous Exercises

74. Prove that Pr(E ∧ F | G)=Pr(E | F ∧ G) · Pr(F | G).

75. Prove that if E

∧ F

and E

∧ F

are independent and F

and F

are

independent, then

Pr(E

∧E

| F

∧ F

)=Pr(E

| F

) · Pr(E

| F

76. (a) Prove that if G is independent of both E and E ∧ F ,then

Pr(E | F ∧ G)=Pr(E | F ).

(b) Give a counterexample showing that the following statement is

false. If G is independent of both E and F ,then

Pr(E | F ∧ G)=Pr(E | F ).

77. (a) Prove that

Pr(E | F ) ≤ Pr(E) ⇔ Pr(F | E) ≤ Pr(F ).

(b) More generally, prove that

Pr(E | F ∧ G) ≤ Pr(E | G) ⇔ Pr(F | E ∧ G) ≤ Pr(F | G).

78. Prove that if M ≤ ψ ≤ ϕ and M is a minterm of ϕ,thenM is also a

minterm of ψ.

79. Prove Lemma H.2(iii) and (iv): if ρ is a partial valuation and W aset

of variables such that ρ(W )=W ,then

(a) ρ(ϕ)

−W

= ρ(ϕ

−W

(b) ρ(ϕ)=1iﬀρ(ϕ

−W

)=1.

80. For deﬁnitions and notation, see Supplementary Lecture H. Let ϕ be

aCNFformulaovervariablesX and ρ : X → X ∪{0, 1} a partial

valuation. Let Y be the set of variables that are not assigned by ρ,and

let N be a term over Y .IfN is a minterm of ρ(ϕ), then there exists a

minterm M of ϕ such that N = ρ(M).

Miscellaneous Exercises 305

81. For deﬁnitions and notation, see Supplementary Lecture H. Consider

random partial valuations ρ that assign 0 or 1 to each variable inde-

pendently with probability

(1 − p) each or leave it unassigned with

probability p.GiveCNFformulasϕ and ψ and s ≥ 0 such that

Pr(∃M ∈ m(ρ(ϕ)) |M |≥s)

< Pr(∃M ∈ m(ρ(ϕ)) |M |≥s | ρ(ψ)=1).

Thus conditioning on a formula becoming equivalent to 1 does not always

make it less likely that there exists a large minterm.

82. (a) Let X

be independent real-valued random variables, 1 ≤ i ≤ n.

Show that the expected value of their product is the product of

their expected values.

(b) Show that (a) is false without the independence assumption.

83. Prove the Markov bound (I.1): for a nonnegative random variable X

with mean µ = EX,

Pr(X ≥ k) ≤ µ/k.

84. Prove the Chebyshev bound (I.2): for a random variable X with mean

µ = EX and standard deviation σ =

E((X −µ)

), for any δ ≥ 1,

Pr(|X − µ|≥δσ) ≤ δ

−2

85. Prove that the standard deviation of n Bernoulli trials with success

probability p is

np(1 − p).

86. Using (a) the Chebyshev bound (I.2), and (b) the Chernoﬀ bound (I.7),

estimate the probability that the number of successes in n Bernoulli

trials with success probability p is less than half the mean.

87. Show that the three alternative forms of the Chernoﬀ bound (I.3), (I.4)

and (I.6) are equivalent.

88. Prove the Chernoﬀ bounds (I.7)–(I.9) for the lower tail.