Transcription
INTRODUCTION TO THETHEORY OF COMPUTATION,SECOND EDITIONMICHAEL SIPSERMassachusettsInstitute of TechnologyTHOMSONCOURSE TECHNOLOGYAustralia * Canada * Mexico * Singapore * Spain * United Kingdom * United States
THOIVISONCOURSE TECHNOLOGYIntroduction to the Theory of Computation,Second Editionby Michael SipserSenior Product Manager:Alyssa PrattAssociate Product Manager:Mirella MisiaszekExecutive Editor:Mac MendelsohnEditorial Assistant:Jennifer SmithAssociate Production Manager:Aimee PoirierSenior Manufacturing Coordinator:Trevor KallopSenior Marketing Manager:Karen SeitzCover Designer:Steve DeschesneThomsonCourse Technology, a division ofThomson Learning, Inc. ThomsonLearningTM is a trademark used hereinunder license.For permission to use material from thistext or product, submit a request onlineat Printed in the United States of America1 2 3 45 67 89 QWT No part ofthis work covered by the copyrighthereon may be reproduced or used inany form or by any means graphic,electronic, or mechanical, includingphotocopying, recording, taping, Webdistribution, or information storage andretrieval systems without the writtenpermission of the publisher.Any additional questions aboutpermissions can be submitted by e-mail tothomsonrights DisclaimerThomson Course Technology reservesthe right to revise this publication andmake changes from time to time in itscontent without notice.ISBN 0-534-95097-3
CONTENTSPreface to the First EditionxiTo the student .xiTo the educator .xiiThe first edition . xiiiFeedback to the author .xiiiAcknowledgments . xivPreface to the Second Edition0xviiIntroduction0.1 Automata, Computability, and Complexity . . . . . . . . . . . . .Complexity theory .Computability theory .Automata theory .0.2 Mathematical Notions and Terminology .Sets .Sequences and tuples .Functions and relations .Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Strings and languages . . . . . . . . . . . . . . . . . . . . . . .Boolean logic .Summary of mathematical terms . . . . . . . . . . . . . . . . .0.3 Definitions, Theorems, and Proofs . .Finding proofs . . . . . . . . . . . . . . . . . . . . . . . . . . .0.4 Types of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . .Proof by construction .Proof by contradiction . . . . . . . . . . . . . . . . . . . . . . .Proof by induction .Exercises, Problems, and Solutions .v11223336710131416171721221212225
ViCONTENTSPart One: Automata and Languages291 Regular Languages1.1 Finite Automata.Formal definition of a finite automaton .Examples of finite automata .Formal definition of computation .Designing finite automata .The regular operations .1.2 Nondeterminism .Formal definition of a nondeterministic finite aut tomatonEquivalence of NFAs and DFAs .Closure under the regular operations .1.3 Regular Expressions .Formal definition of a regular expression .Equivalence with finite automata .1.4 Nonregular Languages .The pumping lemma for regular languages . . .Exercises, Problems, and Solutions .2Context-Free Languages2.1 Context-free Grammars .Formal definition of a context-free grammar . .Examples of context-free grammars .Designing context-free grammars .Ambiguity . . . . . . . . . . . . . . . . . . . . .Chomsky normal form .2.2 Pushdown Automata .Formal definition of a pushdown automaton . . .Examples of pushdown automata .Equivalence with context-free grammars .2.3 Non-context-free Languages .The pumping lemma for context-free languages.Exercises, Problems, and Solutions .Part Two: Computability 031041051061091111121151231231281351373 The Church-Turing Thesis3.1 Turing Machines .137Formal definition of a Turing machine .139Examples of Turing machines .1423.2 Variants of Turing Machines . . . . . . . . . . . . . . . . . . . . . 148Multitape Turing machines .148Nondeterministic Turing machines . 150Enumerators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
CONTENTS3.3ViiEquivalence with other models . 153The Definition of Algorithm . 154Hilbert's problems .154Terminology for describing Turing machines . . . . . . . . . . 156Exercises, Problems, and Solutions .1594 Decidability4.1 Decidable Languages .Decidable problems concerning regular languages .Decidable problems concerning context-free languages . . . .4.2 The Halting Problem .The diagonalization method . . . . . . . . . . . . . . . . . .The halting problem is undecidable . . . . . . . . . . . . . .A Turing-unrecognizable language . . . . . . . . . . . . . . .Exercises, Problems, and Solutions .1651661661701731741791811825 Reducibility1875.1 Undecidable Problems from Language Theory .188Reductions via computation histories .1925.2 A Simple Undecidable Problem .1995.3 Mapping Reducibility . . . . . . . . . . . . . . . . . . . . . . . . 206Computable functions . . . . . . . . . . . . . . . . . . . . . . . 206Formal definition of mapping reducibility . . 207Exercises, Problems, and Solutions .2116Advanced Topics in Computability Theory2176.1 The Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . 217Self-reference .218Terminology for the recursion theorem . . . . . . . . . . . . . 221Applications . 2226.2 Decidability of logical theories . 224A decidable theory .227An undecidable theory .2296.3 Turing Reducibility . . . . . . . . . . . . . . . . . . . . . . . . . . 2326.4 A Definition of Information . . . . . . . . . . . . . . . . . . . . . 233Minimal length descriptions . . 234Optimality of the definition . . . . . . . . . . . . . . . . . . . . 238Incompressible strings and randomness . . 239Exercises, Problems, and Solutions .242Part Three: Complexity Theory2457 Time Complexity7.1 Measuring Complexity .Big-O and small-o notation .247. 247248
ViiiCONTENTS7.27.37.47.589Analyzing algorithms . 251Complexity relationships among models . 254The Class P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256Polynomial time . . . . . . . . . . . . . . . . . . . . . . . . . . 256Examples of problems in P .258The Class NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264Examples of problems in NP .267The P versus NP question .269NP-completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . 271Polynomial time reducibility .272Definition of NP-completeness . 276The Cook-Levin Theorem . . . . . . . . . . . . . . . . . . . . 276Additional NP-complete Problems .283The vertex cover problem . . . . . . . . . . . . . . . . . . . . . 284The Hamiltonian path problem . . 286The subset sum problem .291Exercises, Problems, and Solutions .294Space Complexity8.1 Savitch's Theorem .8.2 The Class PSPACE .8.3 PSPACE-completeness . . . . . . . . . . . . . .The TQBF problem . . . . . . . . . . . . . . .Winning strategies for games . . . . . . . . . .Generalized geography . .8.4 The Classes L and NL .8.5 NL-completeness . . . . . . . . . . . . . . . . .Searching in graphs .8.6 NL equals coNl .Exercises, Problems, and Solutions . . . . . . . . . . . . . . . . . . . . .303.305.308. . . 309. . . 310. . . 313315320. . . 323325. 326328Intractability9.1 Hierarchy Theorems .Exponential space completeness . .9.2 Relativization .Limits of the diagonalization method .9.3 Circuit Complexity .Exercises, Problems, and Solutions .33533634334834935136010 Advanced topics in complexity theory36510.1 ApproximationAlgorithms .36510.2 Probabilistic Algorithms .368The class BPP . 368Primality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371Read-once branching programs . 37610.3 Alternation .380
CONTENTSAlternating time and space . .The Polynomial time hierarchy10.4 Interactive Proof Systems .Graph nonisomorphism .Definition of the model .IP PSPACE .10.5 Parallel Computation.Uniform Boolean circuits .The class NC .P-completeness . . . . . . . .10.6 Cryptographyh.y.Secret keys .Public-key cryptosystems . .One-way functions .Trapdoor functions .Exercises, Problems, and Solutions 1Selected Bibliography415Index421
PREFACE TO THEFIRST EDITIONTO THE STUDENTWelcome!You are about to embark on the study of a fascinating and important subject:the theory of computation. It comprises the fundamental mathematical properties of computer hardware, software, and certain applications thereof. In studying this subject we seek to determine what can and cannot be computed, howquickly, with how much memory, and on which type of computational model.The subject has obvious connections with engineering practice, and, as in manysciences, it also has purely philosophical aspects.I know that many of you are looking forward to studying this material butsome may not be here out of choice. You may want to obtain a degree in computer science or engineering, and a course in theory is required-God knowswhy. After all, isn't theory arcane, boring, and worst of all, irrelevant?To see that theory is neither arcane nor boring, but instead quite understandable and even interesting, read on. Theoretical computer science does havemany fascinating big ideas, but it also has many small and sometimes dull detailsthat can be tiresome. Learning any new subject is hard work, but it becomeseasier and more enjoyable if the subject is properly presented. My primary objective in writing this book is to expose you to the genuinely exciting aspects ofcomputer theory, without getting bogged down in the drudgery. Of course, theonly way to determine whether theory interests you is to try learning it.xi
XiiPREFACE TO THE FIRST EDITIONTheory is relevant to practice. It provides conceptual tools that practitioners use in computer engineering. Designing a new programming language for aspecialized application? What you learned about grammarsin this course comesin handy. Dealing with string searching and pattern matching? Rememberfiniteautomata and regular expressions. Confronted with a problem that seems to require more computer time than you can afford? Think back to what you learnedabout NP-completeness. Various application areas, such as modern cryptographicprotocols, rely on theoretical principles that you will learn here.Theory also is relevant to you because it shows you a new, simpler, and moreelegant side of computers, which we normally consider to be complicated machines. The best computer designs and applications are conceived with elegancein mind. A theoretical course can heighten your aesthetic sense and help youbuild more beautiful systems.Finally, theory is good for you because studying it expands your mind. Computer technology changes quickly. Specific technical knowledge, though usefultoday, becomes outdated in just a few years. Consider instead the abilities tothink, to express yourself clearly and precisely, to solve problems, and to knowwhen you haven't solved a problem. These abilities have lasting value. Studyingtheory trains you in these areas.Practical considerations aside, nearly everyone working with computers is curious about these amazing creations, their capabilities, and their limitations. Awhole new branch of mathematics has grown up in the past 30 years to answercertain basic questio