Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms
Подождите немного. Документ загружается.
Ingo Wegener
Complexity Theory
Ingo Wegener
123
Complexity Theory
Exploring the Limits of Efficient Algorithms
Translated from the German by Randall Pruim
With 31 Figures
Library of Congress Control Number: 2005920530
ISBN-10 3-540-21045-8 Springer Berlin Heidelberg New York
ISBN-13 978-3-540-21045-0 Springer Berlin Heidelberg New York
Ingo Wegener
Universität Dortmund
Fachbereich Informatik
Lehrstuhl Informatik II
Baroper Str. 301
44221 Dortmund
Germany
wegener@1s2.cs.uni-dortmund.de
Translated from the German „Komplexitätstheorie – Grenzen der
Effizienz von Algorithmen“ (Springer-Verlag 2003 , ISBN 3-540-00161-1)
by Randall Pruim.
This work is subject to copyright. All rights are reserved, whether the whole or part of the
material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,
recitation, broadcasting, reproduction on microfilm or in any other way, and storage in
data banks. Duplication of this publication or parts thereof is permitted only under the
provisions of the German Copyright Law of September 9, 1965, in its current version, and
permission for use must always be obtained from Springer. Violations are liable for
prosecution under the German Copyright Law.
Springer is a part of Springer Science+Business Media
springeronline.com
© Springer-Verlag Berlin Heidelberg 2005
Printed in Germany
The use of general descriptive names, registered names, trademarks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from
the relevant protective laws and regulations and therefore free for general use.
Cover design: KünkelLopka, Heidelberg
Production: LE-TeX Jelonek, Schmidt & Vöckler GbR, Leipzig
Typesetting: by Randall Prium
Printed on acid-free paper 33/3142/YL - 5 4 3 2 1 0
Preface to the Original German Edition
At least since the development of the theory of NP-completeness, complexity
theory has become a central area of instruction and research within computer
science. The
NP = P-problem represents one of the great intellectual challenges
of the present. In contrast to other areas within computer science, where it is
often suggested that nearly all problems are solvable with the aid of computers,
the goals of complexity theory include showing what computers cannot do.
Delineating the boundary between problems that can be efficiently solved
and those that can only be solved with an unreasonable amount of resources
is a practically relevant question, but so is the structural question of what
determines the complexity or “complicatedness” of problems.
The development of complexity theory is presented in this book as essen-
tially a reaction to algorithmic development. For this reason, the investiga-
tion of practically important optimization problems plays a predominant role.
From this algorithmic perspective, reduction concepts can be thought of as
methods to solve problems with the help of algorithms for other problems.
From this it follows conversely that we can derive the difficulty of a problem
from the difficulty of other problems.
In this book we choose an unusual approach to the central concept of non-
determinism. The usual description, based on computers that guess a correct
computation path or for which a suitable computation path exists, is often
confusing to students encountering nondeterminism for the first time. Here
this description is replaced with an introduction to randomized algorithms.
Nondeterminism is then simply the special case of one-sided error with an
error-rate that may be larger than is tolerable in applications. In this presen-
tation, nondeterministic algorithms can be run on normal computers, but do
not provide a satisfactory solution to problems. Based on experience, we are
hopeful that this algorithmic approach will make it simpler for students to
grasp the concept of nondeterminism.
Since this is not intended to be a research monograph, the content has been
limited to results that are important and useful for students of computer sci-
ence. In particular, this text is aimed at students who want an introduction
VI Preface
to complexity theory but do not necessarily plan to specialize in this area. For
this reason, an emphasis has been placed on informal descriptions of the proof
ideas, which are, of course, followed by complete proofs. The emphasis is on
modern themes like the PCP-theorem, approximation problems, randomiza-
tion, and communication complexity at the expense of structural and abstract
complexity theory.
The first nine chapters describe the foundation of complexity theory. Be-
yond that, instructors can choose various emphases:
• Chapters 10, 13, and 14 describe a more classically oriented introduction
to complexity theory,
• Chapters 11 and 12 treat the complexity of approximation problems, and
• Chapters 14, 15, and 16 treat the complexity of Boolean functions.
Many ideas have come together in this text that arose in conversations.
Since it is often no longer possible to recall where, when, and with whom
these conversations were held, I would like to thank all those who have dis-
cussed with me science in general and complexity theory in particular. Many
thanks to Beate Bollig, Stefan Droste, Oliver Giel, Thomas Hofmeister, Mar-
tin Sauerhoff, and Carsten Witt, who read the [original German] manuscript
and contributed to improvements through their critical comments, and to Al-
ice Czerniejewski, Danny Rozynski, Marion Scheel, Nicole Skaradzinski, and
Dirk Sudholt for their careful typesetting.
Finally, I want to thank Christa for not setting any limits on the time I
could spend on this book.
Dortmund/Bielefeld, January 2003 Ingo Wegener
Preface to the English Edition
This book is the second translation project I have undertaken for Springer.
My goal each time has been to produce a text that will serve its new audience
as well as the original book served its audience. Thus I have tried to mimic
as far as possible the style and “flavor” of the original text while making the
necessary adaptations. At the same time, a translation affords an opportunity
to make some improvements, which I have done in consultation with the
original author. And so, in some sense, the result is a translation of a second
edition that was never written.
Most of the revisions to the book are quite minor. Some bibliography
items have been added or updated; a number of German sources have been
deleted. Occasionally I have added or rearranged a paragraph, or included
some additional detail, but for the most part I have followed the original
quite closely. Where I found errors in the original, I have tried to fix them; I
hope I have corrected more than I have introduced.
It is always a good feeling to come to the end of a large project like this
one, and in looking back on the project there are always a number of people
to thank. Much of the work done to prepare the English edition of this book
was done while visiting the University of Ulm in the first half of 2004. The
last revisions and final touches were completed during my subsequent visit at
the University of Michigan. I would like to thank all my colleagues at both
institutions for their hospitality during these visits.
A writer is always the worst editor of his own writing, so for reading
portions of the text, identifying errors, and providing various suggestions for
improvement, I want to thank Beate Bollig, Stefan Droste, Jeremy Frens, Judy
Goldsmith, Andr´e Gronemeier, Jens J¨agersk¨upper, Thomas Jansen, Marcus
Schaefer, Tobias Storch, and Dieter van Melkebeek, each of whom read one
or more chapters. In addition, my wife, Pennylyn, read nearly the entire
manuscript. Their volunteered efforts have helped to ensure a more accurate
and stylistically consistent text. A list of those (I hope few) errors that have
escaped detection until after the printing of the book will be available at
VIII Preface
ls2-www.cs.uni-dortmund.de/monographs/ct
Finally, a special thanks goes to Ingo Wegener, who not only wrote the
original text but also responded to my comments and questions, and read the
English translation with a careful eye for details; and to Hermann Engesser
and Dorothea Glaunsinger at Springer for their encouragement, assistance,
and patience, and for a fine Kaffeestunde on a sunny afternoon in Heidelberg.
Ann Arbor, January 2005 Randall Pruim
It is possible to write a research monograph in a non-native language. In
fact, I have done this before. But a textbook with a pictorial language needs
a native speaker as translator. Moreover, the translator should have a good
feeling for the formulations and a background to understand and even to shape
and direct the text. Such a person is hard to find, and it is Randall Pruim who
made this project possible and, as I am convinced, in a perfect way. Indeed,
he did more than a translation. He found some mistakes and corrected them,
and he improved many arguments. Also thanks to Dorothea Glaunsinger and
Hermann Engesser from Springer for their enthusiastic encouragement and for
their suggestion to engage Randall Pruim as translator.
Bielefeld/Dortmund, January 2005 Ingo Wegener
Contents
1 Introduction ............................................... 1
1.1 WhatIsComplexityTheory? ............................. 1
1.2 DidacticBackground..................................... 5
1.3 Overview............................................... 6
1.4 AdditionalLiterature .................................... 10
2 Algorithmic Problems & Their Complexity ................ 11
2.1 WhatAreAlgorithmicProblems? ......................... 11
2.2 Some Important Algorithmic Problems . . . . . . . . . . . . . . . . . . . . . 13
2.3 Measuring Computation Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 TheComplexityofAlgorithmicProblems................... 22
3 Fundamental Complexity Classes .......................... 25
3.1 The Special Role of Polynomial Computation Time . . . . . . . . . . 25
3.2 RandomizedAlgorithms.................................. 27
3.3 The Fundamental Complexity Classes for Algorithmic Problems 30
3.4 The Fundamental Complexity Classes for Decision Problems . . 35
3.5 Nondeterminism as a Special Case of Randomization . . . . . . . . . 39
4 Reductions – Algorithmic Relationships Between Problems 43
4.1 When Are Two Problems Algorithmically Similar? . . . . . . . . . . . 43
4.2 Reductions Between Various Variants of a Problem . . . . . . . . . . 46
4.3 ReductionsBetweenRelatedProblems ..................... 49
4.4 ReductionsBetweenUnrelatedProblems ................... 53
4.5 TheSpecial RoleofPolynomial Reductions ................. 60
5 The Theory of NP-Completeness .......................... 63
5.1 Fundamental Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 ProblemsinNP ......................................... 67
5.3 AlternativeCharacterizationsofNP ....................... 69
5.4 Cook’s Theorem......................................... 70
XContents
6 NP-complete and NP-equivalent Problems ................. 77
6.1 Fundamental Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 TravelingSalesperson Problems ........................... 77
6.3 KnapsackProblems...................................... 78
6.4 PartitioningandScheduling Problems...................... 80
6.5 Clique Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.6 TeamBuildingProblems ................................. 83
6.7 ChampionshipProblems.................................. 85
7 The Complexity Analysis of Problems ..................... 89
7.1 The Dividing Line Between Easy and Hard . . . . . . . . . . . . . . . . . 89
7.2 Pseudo-polynomial Algorithms and Strong NP-completeness . . 93
7.3 An Overview of the NP-completeness Proofs Considered . . . . . . 96
8 The Complexity of Approximation Problems – Classical
Results .................................................... 99
8.1 Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.2 ApproximationAlgorithms ...............................103
8.3 TheGapTechnique......................................106
8.4 Approximation-Preserving Reductions . . . . . . . . . . . . . . . . . . . . . . 109
8.5 CompleteApproximationProblems ........................112
9 The Complexity of Black Box Problems ...................115
9.1 BlackBoxOptimization..................................115
9.2 Yao’sMinimaxPrinciple .................................118
9.3 Lower Bounds for Black Box Complexity . . . . . . . . . . . . . . . . . . . 120
10 Additional Complexity Classes .............................127
10.1 Fundamental Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
10.2 Complexity Classes Within NP and co-NP . . . . . . . . . . . . . . . . . . 128
10.3 Oracle Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
10.4 ThePolynomialHierarchy ................................132
10.5 BPP,NP,andthePolynomialHierarchy....................138
11 Interactive Proofs .........................................145
11.1 Fundamental Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
11.2 InteractiveProof Systems ................................147
11.3 Regarding the Complexity of Graph Isomorphism Problems . . . 148
11.4 Zero-KnowledgeProofs...................................155
12 The PCP Theorem and the Complexity of Approximation
Problems ..................................................161
12.1 RandomizedVerificationofProofs .........................161
12.2 ThePCPTheorem ......................................164
12.3 The PCP Theorem and Inapproximability Results . . . . . . . . . . . 173
12.4 The PCP Theorem and APX-Completeness . . . . . . . . . . . . . . . . . 177
Contents XI
13 Further Topics From Classical Complexity Theory .........185
13.1 Overview...............................................185
13.2 Space-Bounded Complexity Classes . . . . . . . . . . . . . . . . . . . . . . . . 186
13.3 PSPACE-completeProblems..............................188
13.4 Nondeterminism and Determinism in the Context of Bounded
Space ..................................................191
13.5 Nondeterminism and Complementation with Precise Space
Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
13.6 Complexity Classes Within P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
13.7 TheComplexity of Counting Problems .....................198
14 The Complexity of Non-uniform Problems .................201
14.1 Fundamental Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
14.2 The Simulation of Turing Machines By Circuits . . . . . . . . . . . . . 204
14.3 The Simulation of Circuits by Non-uniform Turing Machines . . 206
14.4 Branching Programs and Space Bounds . . . . . . . . . . . . . . . . . . . . 209
14.5 PolynomialCircuitsforProblemsinBPP...................211
14.6 Complexity Classes for Computation with Help . . . . . . . . . . . . . 212
14.7 Are There Polynomial Circuits for all Problems in NP? . . . . . . . 214
15 Communication Complexity ...............................219
15.1 TheCommunicationGame ...............................219
15.2 Lower Bounds for Communication Complexity . . . . . . . . . . . . . . 223
15.3 NondeterministicCommunicationProtocols.................233
15.4 Randomized Communication Protocols . . . . . . . . . . . . . . . . . . . . . 238
15.5 Communication Complexity and VLSI Circuits . . . . . . . . . . . . . . 246
15.6 Communication Complexity and Computation Time . . . . . . . . . 247
16 The Complexity of Boolean Functions .....................251
16.1 Fundamental Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
16.2 CircuitSize.............................................252
16.3 CircuitDepth...........................................254
16.4 The Size of Depth-Bounded Circuits . . . . . . . . . . . . . . . . . . . . . . . 259
16.5 The Size of Depth-Bounded Threshold Circuits . . . . . . . . . . . . . . 264
16.6 TheSizeof BranchingPrograms...........................267
16.7 ReductionNotions.......................................271
Final Comments ...............................................277
A Appendix ..................................................279
A.1 Orders of Magnitude and O-Notation . . . . . . . . . . . . . . . . . . . . . . 279
A.2 Results from Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 283
References .....................................................295
Index ..........................................................301