Introduction to the theory of computation

INTRODUCTIO N T O TH E

THEOR Y O F COMPUTATIO N

MICHAE L SIPSE R

Massachusetts Institute of Technology

DAI HOC THAI NGUYEN

TRUNG TAM HOC LIE U

P W S PUBLISHIN G COMPAN Y

l(T)P • An International Thomson Publishing Company

Boston • Albany • Bonn • Cincinnati • Detroit • London • Madrid

Melbourne • Mexico City • New York • Pacific Grove • Paris

San Francisco • Singapore • Tokyo • Toronto • Washington

PWS PUBLISHING COMPANY

20 Park Plaza, Boston, MA 02116-4324

Copyright © 1997 by PWS Publishing Company.

a division of International Thomson Publishing Inc.

All rights reserved. No part of this book may be reproduced, stored in a retrieval system.

or transcribed in any form or by any means - electronic, mechanical, photocopying, recording.

or otherwise - without the prior written permission of PWS Publishing Company.

I(T^)PrM

International Thomson Publishing

The trademark ITP is used under license.

Sponsoring Editor: David Dietz

Editorial Assistant: Susan Garland

Marketing Manager: Nathan Wilbur

Production Manager: Elise S. Kaiser

Manufacturing Buyer: Andrew Christensen

Interior Designer: Catherine Hawkes

Cover Designer: Diane Levy

Cover Art: "The Unknown Leonardo"© EMB

Prepress: Pure Imaging

Text Printer/Binder: CourierfWestford

Cover Printer: Coral Graphic Services, Inc.

For more information, contact:

PWS Publishing Company

20 Park Plaza

Boston, MA 02116

International Thomson Publishing Europe

Berkshire House 168-173

High Holborn

London WC1V 7AA

England

Thomas Nelson Australia

102 Dodds Street

South Melbourne, 3205

Victoria. Australia

Nelson Canada

1120Birchmont Road

Scarborough, Ontario

Canada M1K 504

Library of Congress

Cataloging-in-Publication Data

Sipser. Michael.

Introduction to the theory of computation /

Michael Sipser.

p. cm.

Includes bibliographical references and index.

ISBN 0-534-94728-X

1. Machine theory. 2. Computational

complexity. I. Title

QA267.S56 1996b 96-35322

511.3--dc20 CIP

Printed and bound in the United States of America.

02 03 10 9

International Thomson Editores

Campos Eliseos 385. Piso 7

Col. Polanco

11560 Mexico D.F., Mexico

International Thomson Publishing GmbH

Konigswinterer Strasse 418

53227 Bonn. Germany

International Thomson Publishing Asia

221 Henderson Road

#05-10 Henderson Building

Singapore 0315

International Thomson Publishing Japan

Hirakawacho Kyowa Building. 31

2-2-1 Hirakawacho

Chiyoda-ku. Tokyo 102

Japan

CONTENT S

Preface xi

To the student xi

To the educator xii

The current edition xiii

Feedback to the author xiii

Acknowledgments xiv

0 Introduction 1

0.1 Automata, Computability, and Complexity 1

Complexity theory 2

Computability theory 2

Automata theory 3

0.2 Mathematical Notions and Terminology 3

Sets 3

Sequences and tuples 6

Functions and relations 7

Graphs 10

Strings and languages 13

Boolean logic 14

Summary of mathematical terms 16

0.3 Definitions, Theorems, and Proofs 17

Finding proofs 17

0.4 Types of Proof 21

Proof by construction 21

Proof by contradiction 21

Proof by induction 23

Exercises and Problems 25

Part One: Automata and Languages 29

1 Regular Languages 31

L I Finite Automata 31

Formal definition of a finite automaton 35

Examples of finite automata 37

v

Vi CONTENTS

Formal definition of computation 40

Designing finite automata 41

The regular operations 44

1.2 Nondeterminism 4"

Formal definition of a nondeterministic finite automaton . .. . 53

Equivalence of NFAs and DFAs 54

Closure under the regular operations 58

1.3 Regular Expressions 63

Formal definition of a regular expression 64

Equivalence with finite automata 66

1.4 Nonregular Languages 77

The pumping lemma for regular languages 77

Exercises and Problems 83

2 Context-Free Languages 91

2.1 Context-free Grammars 92

Formal definition of a context-free grammar 94

Examples of context-free grammars 95

Designing context-free grammars 96

Ambiguity 97

Chomsky normal form 98

2.2 Pushdown Automata 101

Formal definition of a pushdown automaton 103

Examples of pushdown automata 104

Equivalence with context-free grammars 106

2.3 Non-context-free Languages 115

The pumping lemma for context-free languages 115

Exercises and Problems 119

Part Two: Computability Theory 123

3 The Church-Turing Thesis 125

3.1 Turing Machines 125

Formal definition of a Turing machine 127

Examples of Turing machines 130

3.2 Variants of Turing Machines 136

Multitape Turing machines 136

Nondeterministic Turing machines 138

Enumerators 140

Equivalence with other models 141

3.3 The Definition of Algorithm 142

Hilbert's problems 142

Terminology for describing Turing machines 144

Exercises and Problems 14"

CONTENTS Vli

4 Decidability 151

4.1 Decidable Languages 152

Decidable problems concerr ing regular languages 152

Decidable problems concerr ing context-free languages 156

4.2 The Halting Problem 159

The diagonalization method 160

The halting problem is und( cidable 165

A Turing-unrecognizable lai guage 167

Exercises and Problems 168

5 Reducibility 171

5.1 Undecidable Problems from L mguage Theory 172

Reductions via computation histories 176

5.2 A Simple Undecidable Problen 183

5.3 Mapping Reducibility 189

Computable functions 190

Formal definition of mappir g reducibility 191

Exercises and Problems 195

6 Advanced Topics in Computabilil y Theory 197

6.1 The Recursion Theorem 197

Self-reference 198

Terminology for the recursii >n theorem 201

Applications 202

6.2 Decidability of logical theories 204

A decidable theory 206

An undecidable theory 209

6.3 Turing Reducibility 211

6.4 A Definition of Information 213

Minimal length descriptions 214

Optimality of the definition 217

Incompressible strings and i andomness 217

Exercises and Problems 220

Part Three: Complexity Theo ty 223

7 Time Complexity 225

7.1 Measuring Complexity 225

Big-0 and small-o notation 226

Analyzing algorithms 229

Complexity relationships an long models 231

7.2 The Class P 234

Polynomial time 234

Examples of problems in P 236

7.3 The Class NP 241

viH CONTENTS

Examples of problems in NP 245

The P versus XP question 24

7.4 XP-completeness 24

s

Polynomial time reducibility 249

Definition of XP-completeness 253

The Cook-Levin Theorem 254

7.5 Additional XP-complete Problems 260

The vertex cover problem 261

The Hamiltonian path problem 262

The subset sum problem 268

Exercises and Problems 2,1

8 Space Complexity 277

8.1 Savitch's Theorem 279

8.2 The Class PSPACE 281

8.3 PSPACE-completeness 283

The TQBF problem 283

Winning strategies for games 287

Generalized geography 289

8.4 The Classes L and X L .' 294

8.5 XL-completeness 29"

Searching in graphs 298

8.6 X L equals coXL 300

Exercises and Problems 302

9 Intractability 305

9.1 Hierarchy Theorems 306

Exponential space completeness 313

9.2 Relativization 318

Limits of the diagonalization method 319

9.3 Circuit Complexity 321

Exercises and Problems 330

10 Advanced topics in complexity theory 333

10.1 Approximation Algorithms 333

10.2 Probabilistic Algorithms 335

The class BPP 336

Primality 339

Read-once branching programs 343

10.3 Alternation 348

Alternating time and space 349

The Polynomial time hierarchy 353

10.4 Interactive Proof Systems 354

Graph nonisomorphism 355

Definition ot the model 355

IP = PSPACE 357

CONTENTS i x

10.5 Parallel Computation 366

Uniform Boolean circuits 367

The class NC 369

P-completeness 371

10.6 Cryptography 372

Secret keys 372

Public-key cryptosystems 374

One-way functions 374

Trapdoor functions 376

Exercises and Problems 378

Selected Bibliography 381

Index 387