Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms
Подождите немного. Документ загружается.
292 A Appendix
Prob(X ≥ (1 + ε) · E(X)) becomes very small as n increases. The Markov
Inequality only provides the following estimate
Prob (X ≥ (1 + ε) · E(X)) ≤ 1/(1 + ε) ,
which is independent of n. With the Chebychev Inequality we obtain
Prob (X ≥ (1 + ε) · E(X)) = Prob (X − E(X) ≥ ε · E(X))
≤ Prob (|X − E(X)|≥ε · E(X))
≤ V (X)/
ε
2
· E(X)
2
= ε
−2
· n
−1
.
So the probability we are considering is polynomially small. The Chernoff
Inequality, which we will derive shortly, will show that the probability is in
fact strictly exponential small. The Chernoff Inequality also follows from the
Markov Inequality. While for the Chebychev Inequality random variables were
squared, or more generally the kth power Y
k
was considered, for the Chernoff
Inequality we will consider the random variable e
−Y
. The stronger curvature
of the exponential function as compared to polynomials makes a significantly
better estimate possible, but only for certain random variables.
Theorem A.2.11 (Chernoff Inequality). Suppose 0 <p<1 and X =
X
1
+ ···+ X
n
for independent random variables X
1
,...,X
n
with Prob(X
i
=
1) = p and Prob(X
i
=0)=1− p. Then E(X)=np and for all δ ∈ (0, 1) we
have
Prob (X ≤ (1 − δ) · E(X)) ≤ e
− E(X)δ
2
/2
.
Proof. The statement about E(X) follows from the linearity of expected value
and E(X
i
)=p (Remark A.2.3).
Anumbert>0 will be chosen later in the proof. Since the function
x → e
−tx
is strictly monotonically decreasing, X ≤ (1−δ) ·E(X) is equivalent
to e
−tX
≥ e
−t(1−δ)E(X)
. So by the Markov Inequality we have
Prob (X ≤ (1 − δ) · E(X)) = Prob
e
−tX
≥ e
−t(1−δ)E(X)
≤ E
e
−tX
/e
−t(1−δ)E(X)
.
Now we compute E(e
−tX
). Since X
1
,...,X
n
are independent, this is the ran-
dom variables e
−tX
1
,...,e
−tX
n
are also independent. Thus
E
e
−tX
=E
e
−t(X
1
+···+X
n
)
=E
%
1≤i≤n
e
−tX
i
=
%
1≤i≤n
E(e
−tX
i
)
.
And since X
i
only takes on the values 0 and 1, it follows that
E
e
−tX
i
=1· (1 − p)+e
−t
· p
=1+p (e
−t
− 1) .
A.2 Results from Probability Theory 293
It follows that
E
e
−tX
=
1+p(e
−t
− 1)
n
.
By a simple result from calculus, 1 + x<e
x
for all x<0, and since t>0,
p (e
−t
− 1) < 0and
E
e
−tX
<e
p(e
−t
−1)n
= e
(e
−t
−1)·E(X)
.
In the last step we took advantage of the fact that E(X)=np.Nowwelet
t := − ln(1 − δ). Then t>0ande
−t
− 1=−δ.Thus
E
e
−tX
<e
−δ·E(X)
.
Finally, we substitute this result into our first estimate and obtain
Prob (X ≤ (1 − δ)E(X)) <e
−δ·E(X)
/e
(ln(1−δ))(1−δ)E(X)
= e
(−(1−δ) ln(1−δ)−δ)E(X)
.
From the Taylor series for x ln x it follows that
(1 − δ)ln(1− δ) > −δ + δ
2
/2 .
Inserting this leads to the Chernoff Inequality.
We return now to our example, where p =1/2. Then X ≥ (1 + ε) · E(X)
has the same probability as X ≤ (1 − ε) · E(X), since X is symmetrically
distributed about E(X). For a coin toss, we are simply reversing the roles of
the two sides of the coin. Thus
Prob (X ≥ (1 + ε) · E(X)) ≤ e
−ε
2
n/4
is in fact strictly exponential small.
Frequently we encounter the following problem when investigating ran-
domized algorithms. Such an algorithm may proceed in phases. Each phase
has a probability of p of succeeding, in which case we stop the algorithm.
Otherwise a new phase is begun that is completely independent of the pre-
ceding phases. Let X be a random variable that takes on the value t if the first
success occurs in the tth phase. Since the phases are completely independent,
Prob(X = t)=q
t−1
p,
where q := 1 − p. That is, outcome X = t is equivalent to the failure of
the first t − 1 phases followed by success in the tth phase. This probability
distribution is known as the geometric distribution. We are interested in the
expected value of this distribution.
294 A Appendix
Theorem A.2.12. Let X be geometrically distributed with parameter p. Then
E(X)=1/p.
Proof. By definition
E(X)=
1≤k<∞
k · q
k−1
· p
= p · ( q
0
+ q
1
+ q
1
+ q
2
+ q
2
+ q
2
+ q
3
+ q
3
+ q
3
+ q
3
+ ··· ) .
The first column has the value 1/(1 − q)=1/p. Analogously, the value of the
ith column (factor out q
i−1
)isq
i−1
/p.So
E(X)=p ·
1
p
·
1≤i<∞
q
i−1
=
1
p
.
References
1. Agrawal, M., Kayal, N. and Saxena, N. (2002). PRIMES is in P. Tech.
Report Dept. of Computer Science and Engineering. Indian Inst. of Tech-
nology Kanpur.
2. Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993). Network Flows. The-
ory, Algorithms and Applications. Prentice–Hall.
3. Alon, N. and Boppana, R.B. (1987). The monotone circuit complexity of
Boolean functions. Combinatorica 7, 1–22.
4. Alon, N. and Spencer, J. (1992). The Probabilistic Method. Wiley.
5. Arora, S. (1997). Nearly linear time approximation schemes for Euclidean
TSP and other geometric problems. Proc. of 38th IEEE Symp. on Foun-
dations of Computer Science, 554–563.
6. Arora, S., Lund, C., Motwani, R., Sudan, M. and Szegedy, M. (1998).
Proof verification and the hardness of approximation problems. Journal
of the ACM 45, 501–555.
7. Arora, S. and Safra, S. (1998). Probabilistic checking of proofs: A new
charaterization of NP. Journal of the ACM 45, 70–122.
8. Aspvall, B. and Stone, R.E. (1980). Khachiyan’s linear programming al-
gorithm. Journal of Algorithms 1, 1–13.
9. Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela,
A. and Protasi, M. (1999). Complexity and Approximation. Springer.
10. Balc´azar, J.L., D´ıaz, J. and Gabarr´o, J. (1988). Structural Complexity.
Springer.
11. Beame, P., Saks, M., Sun, X. and Vee, E. (2003). Time-space trade-off
lower bounds for randomized computation of decision problems. Journal
of the ACM 50, 154–195.
12. Bellare, M., Goldreich, O. and Sudan, M. (1998). Free bits, PCP and non-
approximability – towards tight results. SIAM Journal on Computing 27,
804–915.
13. Bernholt, T., G¨ulich, A., Hofmeister, T., Schmitt, N. and Wegener, I.
(2002). Komplexit¨atstheorie, effiziente Algorithmen und die Bundesliga.
Informatik–Spektrum 25, 488–502.
296 References
14. Boppana, R. and Halld´orsson, M.M. (1992). Approximating maximum
independent sets by excluding subgraphs. BIT 32, 180–196.
15. Clote, P. and Kranakis, E. (2002). Boolean Functions and Computation
Models. Springer.
16. Cook, S.A. (1971). The complexity of theorem proving procedures. Proc.
3rd ACM Symp. on Theory of Computing, 151–158.
17. Dietzfelbinger, M. (2004). Primality Testing in Polynomial Time. LNCS
3000. Springer.
18. Feige, U., Goldwasser, S., Lov´asz, L., Safra, S. and Szegedy, M. (1991).
Approximating clique is almost NP-complete. Proc. of 32nd IEEE Symp.
on Foundations of Computer Science, 2–12.
19. Garey, M.R. and Johnson, D.B. (1979). Computers and Intractability. A
Guide to the Theory of NP-Completeness. W.H. Freeman.
20. Goldmann, M. and Karpinski, M. (1993). Simulating threshold circuits by
majority circuits. Proc. of the 25th ACM Symp. on Theory of Computing,
551–560.
21. Goldreich, O. (1998). Modern Cryptography, Probabilistic Proofs and
Pseudorandomness. Algorithms and Combinatorics, Vol.17. Springer.
22. Goldwasser, S., Micali, S. and Rackoff, C. (1989). The knowledge complex-
ity of interactive proof-systems. SIAM Journal on Computing 18, 186–208.
23. H˚astad, J. (1989). Almost optimal lower bounds for small depth circuits.
In: Micali, S. (ed.) Randomness and Computation. Advances in Comput-
ing Research 5, 143–170. JAI Press.
24. H˚astad, J. (1999). Clique is hard to approximate within n
1−ε
.Acta
Mathematica 182, 105–142.
25. H˚astad, J. (2001). Some optimal inapproximability results. Journal of the
ACM 48, 798–859.
26. Hajnal, A., Maass, W., Pudl´ak, P., Szegedy, M. and Tur´an, G. (1987).
Threshold circuits of bounded depth. Proc. of 28th IEEE Symp. on Foun-
dations of Computer Science, 99–110.
27. Hemaspaandra, L. and Ogihara, M. (2002). The Complexity Theory Com-
panion. Springer.
28. Homer, S. (2001). Computability and Complexity Theory. Springer.
29. Hopcroft, J.E., Motwani, R. and Ullman, J.D. (2001). Introduction to Au-
tomata Theory, Languages and Computation. Addison-Wesley Longman.
30. Hopcroft, J.E. and Ullman, J.D. (1979). Introduction to Automata Theory,
Languages and Computation. Addison-Wesley.
31. Hromkoviˇc, J. (1997). Communication Complexity and Parallel Comput-
ing. Springer.
32. Johnson, D.S. (1974). Approximation algorithms for combinatorial prob-
lems. Journal of Computer and System Sciences 9, 256–278.
33. Kann, V. and Crescenzi, P. (2000). A list of NP-complete optimization
problems. www.nada.kth.se/∼viggo/index-en.html
References 297
34. Karmarkar, N. and Karp, R.M. (1982). An efficient approximation scheme
for the one-dimensional bin packing problem. Proc. of 23rd IEEE Symp.
on Foundations of Computer Science, 312–320.
35. Karp, R.M. (1972). Reducibility among combinatorial problems. In:
Miller, R.E. and Thatcher, J.W. (eds.). Complexity of Computer Com-
putations, 85–103. Plenum Press.
36. Korte, B. and Schrader, R. (1981). On the existence of fast approximation
schemes. In : Nonlinear Programming. Academic Press.
37. Kushilevitz, E. and Nisan, N. (1997). Communication Complexity. Cam-
bridge University Press.
38. Ladner, R.E. (1975). On the structure of polynomial time reducibility.
Journal of the ACM 22, 155–171.
39. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B.
(1985). The Traveling Salesman Problem. A Guided Tour of Combina-
torial Optimization. Wiley.
40. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B.
(1993). Sequencing and Scheduling: Algorithms and Complexity. In:
Graves, S.C., Rinnooy Kan, A.H.G. and Zipkin, P.H. (eds.). Handbook in
Operations Research and Management Science, Vol. 4, Logistics of Pro-
duction and Inventory, 445–522. North–Holland.
41. Levin, L.A. (1973). Universal sorting problems. Problems of Information
Transmission 9, 265–266.
42. Martello, S. and Toth, P. (1990). Knapsack Problems. Wiley.
43. Mayr, E., Pr¨omel, H.J. and Steger, A. (1998) (eds.). Lectures on Proof
Verification and Approximation Algorithms. LNCS 1367. Springer.
44. Miller, G.L. (1976) Riemann’s hypothesis and tests for primality. Journal
of Computer and System Sciences 13, 300–317.
45. Miltersen, P.B. (2001). Derandomizing complexity classes. In Parda-
los, P.M., Rajasekaran, S., Reif, J. and Rolim, J. (eds.). Handbook of
Randomization. Kluwer.
46. Motwani, R. and Raghavan, P. (1995). Randomized Algorithms. Cam-
bridge University Press.
47. Nechiporuk,
´
E.I. (1966) A Boolean function. Soviet Mathematics Doklady
7, 999–1000.
48. Nielsen, M.A. and Chuang, I.L. (2000). Quantum Computation and Quan-
tum Information. Cambridge University Press.
49. Owen, G. (1995). Game Theory. Academic Press.
50. Papadimitriou, C.M. (1994). Computational Complexity. Addison–Wesley.
51. Pinedo, M. (1995). Scheduling: Theory, Algorithms and Systems. Prentice–
Hall.
52. Razborov, A.A. (1987). Lower bounds on the size of bounded depth net-
works over a complete basis with logical addition. Math. Notes of the
Academy of Sciences of the USSR 41, 333–338.
298 References
53. Razborov, A.A. (1990). Lower bounds for monotone complexity of Boolean
functions. American Mathematical Society Translations 147, 75–84.
54. Razborov, A.A. (1995). Bounded arithmetics and lower bounds in Boolean
complexity. In: Clote, P. and Remmel, J. (eds.). Feasible Mathematics II.
Birkh¨auser.
55. Sch¨onhage, A., Grotefeld, A.F.W. and Vetter, E. (1999). Fast Algorithms:
A Multitape Turing Machine Implementation. Spektrum Akademischer
Verlag.
56. Shamir, A. (1992). IP=PSPACE. Journal of the ACM 39, 869–877.
57. Shasha, D. and Lazere, C. (1998). Out of Their Minds. The Lives and
Discoveries of 15 Great Computer Scientists. Copernicus (Springer).
58. Singh, S. (1998). Fermat’s Last Theorem. Fourth Estate.
59. Sipser, M. (1997). Introduction to the Theory of Computation. PWS Pub-
lishing Company.
60. Smolensky, R. (1987). Algebraic methods in the theory of lower bounds
for Boolean circuit complexity. Proc. of 19th ACM Symp. on Theory of
Computing, 77–82.
61. Solovay, R. and Strassen, V. (1977). A fast Monte-Carlo test for primality.
SIAM Journal on Computing 6, 84–85.
62. Stinson, D.R. (1995). Cryptography. Theory and Practice. CRC Press.
63. Stockmeyer, L.J. (1977). The polynomial time hierarchy. Theoretical
Computer Science 3, 1–22.
64. Strassen, V. (1986). The work of Leslie G. Valiant. Proc. of the Int.
Congress of Mathematics, Berkeley, Ca.
65. Thompson, C.D. (1979). Area-time complexity for VLSI. Proc. of 11th
ACM Symp. on Theory of Computing, 81–88.
66. Valiant, L.G. (1979). The complexity of computing the permanent. The-
oretical Computer Science 8, 189–201.
67. van Leeuwen, J. (1990) (ed.). Handbook of Theoretical Computer Science.
Elsevier, MIT Press.
68. Wagner, K. and Wechsung, G. (1986). Computational Complexity. VEB
Deutscher Verlag der Wissenschaften.
69. Wegener, I. (1982). Boolean functions whose monotone complexity is of
size n
2
/log n. Theoretical Computer Science 21, 213–224.
70. Wegener, I. (1987). The Complexity of Boolean Functions. Wiley. Freely
available via http://ls2-www.cs.uni-dortmund.de/∼wegener.
71. Wegener, I. (2000). Branching Programs and Binary Decision Diagrams
– Theory and Applications. SIAM Monographs on Discrete Mathematics
and Applications.
72. Wegener, I. (2002). Teaching nondeterminism as a special case of random-
ization. Informatica Didactica 4 (electronic journal).
73. Yao, A.C. (1977). Probabilistic computations: Towards a unified measure
of complexity. Proc. of 18th Symp. on Foundations of Computer Science,
222–227.
References 299
74. Yao, A.C. (1979). Some complexity questions related to distributed com-
puting. Proc. of 11th ACM Symp. on Theory of Computing, 209–213.
75. Yao, A.C. (2001). Lecture upon receiving the Turing Award. July 8, 2001,
Chersonissos, Crete.
Index
#P 198
#P-complete 199
#Sat 198, see also Sat
δ-close 168
≤
1
see NC
1
-reduction
≤
cd
see AC
0
-reduction
≤
proj
see projection
≤
rop
see read-once projection
≤
log
see logarithmic reduction
⊕ see parity
≤
T
see Turing reduction
≡
T
see Turing equivalent
≤
p
see polynomial reduction
≤
PTAS
see PTAS reduction
≤
rect
see rectangular reduction
ε-optimal 100
3-DM 83
3-Partition 95
3-Sat 51, see also Sat
4-Partition 95
AC
0
260
AC
0
-reduction 271
ACC
0
[m] 263
AC
k
272
Agrawal 68, 128
Ahuja 16, 49
algorithm 18
deterministic 39, 69
nondeterministic 39
pseudo-polynomial time 105
randomized 8, 27, 39, 44, 69, 102
algorithmic complexity 23, 24
Alice 190, 219, 257
Alon 242, 254, 261
alternating counting class 263
AM 151
AND-gate 252
AND-nondeterminism 233
anti-clique 53, see also independent
set
approximation problem 101
approximation ratio 100
APX
∗
102
arithmetization 165
Arora 105, 164, 175
Arthur-Merlin game 151
Aspvall 128
asymptotic FPTAS 105
asymptotic worst-case approximation
ratio 101
Ausiello 10, 114, 164
Aut(G) see automorphism group
automorphism group 149
average-case runtime 23, 28
Bachmann 279
Balc´azar 10
baseball 17
basketball 17
BDD see binary decision diagram
Bellare 164
Bernholt 17
best-fit decreasing 104
BFD see best-fit decreasing
big O notation 162, 279
bin packing problem 15, 47, 48, 52, 80,
178
302 Index
binary decision diagram 9, 209
binary decision tree 10
bit commitment 157
black box 8, 116
black box complexity 117
black box optimization 117
black box problem 116
BMST see bounded-degree minimum
spanning tree
Bob 190, 219, 257
Bollig VI, VII
Boolean
formula 9, 10
function 9, 10
Boppana 103, 254
bounded error 36
bounded-degree minimum spanning tree
78
bounded-error probabilistic polynomial
time 33, see BPP
bouquet 18
BinPacking see bin packing problem
BPP 29, 33, 40
branching program 9, 10, 209, 251, 267
Bundesliga 17, 92
C 35
C-complete 65, 196
C-easy 65
C-equivalent 65
C-hard 65
CAR see carry bit
carry bit 264
CC see clique cover problem
central moment 288
championship problem 16, 53, 54, 68,
85, 91, 94
Chebychev Inequality 291
checkers 190
Chernoff Inequality 33, 242, 292
chess 190
chip 17
Chomsky hierarchy 187
chromatic number 109
Chuang 21
Church-Turing Thesis 20, 22, 25, 26,
45
circuit 9, 10, 201, 251
nondeterministic 213
circuit depth 202, 252, 254
circuit size 252, 260
circuit value problem 196, 272
clause 17
Clique see clique problem
clique 15
clique cover problem 16, 47, 68
clique problem 16, 47, 48, 52, 56, 68,
81, 103, 111, 175, 178, 214, 254
Clote 10
co-C 35
coin toss 31
combinatoric rectangle 224
communication complexity 9, 10, 219,
220
communication game 219
communication matrix 224
communication protocol 220
communication rounds 221
complement 29
complete see C-complete
PSPACE 188
completely independent 285, 286
completeness
NP 7, 10, 77
complexity class 26
composition lemma 173
computable 43, 203
computation
parallel 20
quantum 20
computation path 39
computation time see runtime
conditional probability 284
configuration of a Turing machine 71,
187
conjunction 17
conjunctive (normal) form 17, 74, 260
co-NP
40
consistency test 167, 172
constant depth reduction see
AC
0
-reduction
context-sensitive language 187
Cook 71, 72, 107, 113
Cook’s Theorem 72, 189, 199
counting problem 198
covering problem 15
CP see championship problem
Crescenzi 10, 114, 164