Kozen D.C. Theory of Computation

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

TEXTS IN COMPUTER SCIENCE

Editors

David Gries

Fred B. Schneider

TEXTS IN COMPUTER SCIENCE

Apt and Olderog, Verification of Sequential and Concurrent

Programs, Second Edition

Alagar and Periyasamy, Specification of Software Systems

Back and von Wright, Refinement Calculus: A Systematic

Introduction

Beidler, Data Structures and Algorithms: An Object-

Oriented Approach Using Ada 95

Bergin, Data Structures Programming: With the Standard

Template Library in C++

Brooks, C Programming: The Essentials for Engineers and

Scientists

Brooks, Problem Solving with Fortran 90: For Scientists and

Engineers

Dandamudi, Fundamentals of Computer Organization and

Design

Dandamudi, Introduction to Assembly Language

Programming: For Pentium and RISC Processors, Second

Edition

Dandamudi, Introduction to Assembly Language

Programming: From 8086 to Pentium Processors

Fitting, First-Order Logic and Automated Theorem Proving,

Second Edition

Grillmeyer, Exploring Computer Science with Scheme

Homer and Selman, Computability and Complexity Theory

(continued after index)

Dexter C. Kozen

Theory of Computation

With 75 Illustrations

Dexter C. Kozen

Department of Computer Science

Upson Hall

Cornell University

Ithaca, NY 14853-7501, USA

kozen@cs.cornell.edu

Series Editors:

David Gries

Department of Computer Science

Upson Hall

Cornell University

Ithaca, NY 14853-7501, USA

Fred B. Schneider

Department of Computer Science

Upson Hall

Cornell University

Ithaca, NY 14853-7501, USA

British Library Cataloguing in Publication Data

A catalogue record for this book is available from the British Library

Library of Congress Control Number: 2005937504

ISBN-10: 1-84628-297-7 Printed on acid-free paper

ISBN-13: 978-1-84628-297-3

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the

or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in

accordance with the terms of licences issued by the Copyright Licensing Agency. Enquiries concerning reproduction

outside those terms should be sent to the publishers.

The use of registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific state-

ment, that such names are exempt from the relevant laws and regulations and therefore free for general use.

The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in

this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made.

Printed in the United States of America (HAM)

9 8 7 6 5 4 3 2 1

Springer Science+Business Media

springer.com

To Fra nces

Preface

These are my lecture notes from CS682: Theory of Computation, a one-

semester course for ﬁrst-year graduate students in computer science at Cor-

nell, which I have taught oﬀ and on for many years. I took the course myself

as a PhD student at Cornell from Juris Hartmanis, and his inﬂuence can

be seen in the presentation and selection of topics.

Overview and Goals

The course serves a dual purpose: to cover core material in the founda-

tions of computing for graduate students in computer science preparing

for their PhD qualifying exams, and to provide an introduction to some

more advanced topics in the theory of computational complexity for those

intending to pursue further study in the area. The course is thus a mixture

of core and advanced material.

Most of the course is concerned with computational complexity,orthe

classiﬁcation of computational problems in terms of their inherent complex-

ity. This usually refers to time or space usage on a particular computational

model, but may include other complexity measures as well, such as random-

ness, number of alternations, or circuit size or depth. We include a rigorous

treatment of computational models, including deterministic, nondetermin-

istic, and alternating Turing machines, circuits, probabilistic machines, in-

teractive proof systems, automata on inﬁnite objects, and various logical

formalisms. Also included are various approximation and inapproximation

results and some lower bounds. According to most treatments, the complex-

ity universe stops at polynomial space, but we also look at higher levels of

viii Preface

complexity all the way up through the primitive recursive functions, partial

recursive functions, and the arithmetic and analytic hierarchies.

Despite the title of this book, there are many beautiful areas of theo-

retical computer science that I could not cover for lack of time and space.

Intended Audience

The course is aimed at an audience of advanced undergraduates and ﬁrst-

year graduate students in computer science or mathematics with an interest

in the theory of computation and computational complexity. It may also be

of interest to computer professionals and other scientists who would like to

learn more about the classical foundations of computing and contemporary

research trends.

Familiarity with the content of standard undergraduate courses in algo-

rithms and the theory of computation are helpful prerequisites. In particu-

lar, we make free use of discrete mathematical structures, including graphs,

trees, and dags; O()ando( ) notation; ﬁnite automata, regular expressions,

pushdown automata, and context-free languages; and Turing machines,

computability, undecidability, and diagonalization. There are many good

undergraduate texts that cover this material, for example, [61, 76, 113].

Organization and Features

The course consists of 41 primary lectures and a handful of supplementary

lectures covering more specialized or advanced topics. In my previous texts

[75, 76], the basic unit is a lecture, which is a more or less self-contained

chunk of 4–7 pages. I have received much positive feedback regarding this

organization, so I have stuck with it here. In addition to the lectures, there

are 12 homework sets and several miscellaneous homework exercises of vary-

ing levels of diﬃculty, many with hints and complete solutions.

Acknowledgments

Many people have contributed in many ways to this work, and there is not

enough I can ever say in thanks. First and foremost, I owe an incalculable

debt of gratitude to my wife, Frances, for her constant love, patience, and

forbearance.

My administrative assistants, Rosemary Adessa, Beth Howard, and

Kelly Patwell, deserve special thanks for making sure that the real world

did not escape my attention for too long a period.

The professional staﬀ at Springer, Catherine Brett, Valerie Greco, Nata-

cha Menar, and Wayne Wheeler, have been most accommodating through-

Preface ix

out the entire production process. It has been a pleasure working with

them.

There are many students who over the years have contributed to these

notes and kept me honest. In particular, I would like to thank Kamal Aboul-

Hosn, Adam Arbree, Adam Barth, Yuri Berkovich, Chavdar Botev, Greg

Bronevetsky, Walter Chen, Pablo Fierens, Suman Ganguli, Dan Gross-

man, Vincent Gu, Milos Hasan, Yannet Interian-Fernandez, Aaron Kauf-

man, Omar H. Khan, Lucja Kot, Brian Kulis, Milind Kulkarni, Ashwin

Machanavajjhala, David Martin, Wojtek Moczydlowski, Antonio Montal-

ban, Jonathan Moon, Bryan Renne, Andrew Scukanec, Alexa Sharp, Zoya

Svitkina, and Ryan Williams.

I am especially indebted to my teaching assistants Suresh Chari, Reba

Schuller, and Chaitanya Swamy for their help with proofreading, prepara-

tion of solution sets, and occasional lecturing.

I am grateful to my colleagues Jin-Yi Cai, Robert Constable, Uriel Feige,

John Hopcroft, Jon Kleinberg, Bakhadyr Khoussainov, Stephen Mahaney,

Anil Nerode, Christos Papadimitriou, Ronitt Rubinfeld, Erik Meineche

Schmidt, Bart Selman, Richard Shore, Michael Sipser, and

Eva Tardos

for their interest in this project and for valuable comments and interesting

exercises. Uriel’s and Ronitt’s notes on probabilistically checkable proofs

were an especially useful source. Finally, I wish to express my sincerest

gratitude to Juris Hartmanis, who has taught the course many times, and

who is always an inspiration.

I would be most grateful for suggestions or criticism from readers.

Cornell University Dexter Kozen

Ithaca, New York October 2005

Contents

Preface vii

Lectures 1

1 TheComplexityofComputations......................... 3

2 Time and Space Complexity Classes and Savitch’s Theorem . 11

3 SeparationResults ..................................... 17

4 The Immerman–Szelepcs´enyiTheorem.................... 22

5 Logspace Computability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

6 The Circuit ValueProblem.............................. 30

A TheKnaster–TarskiTheorem ........................... 35

7 Alternation ........................................... 44

8 Problems Complete for PSPACE ........................ 51

9 The Polynomial-TimeHierarchy ......................... 57

10 Moreonthe Polynomial-TimeHierarchy.................. 62

11 ParallelComplexity .................................... 66

12 Relation of NC to Time-SpaceClasses.................... 70

13 Probabilistic Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

14 BPP ⊆ Σ

∩ Π

...................................... 82

B Chinese Remaindering.................................. 86

C Complexity ofPrimalityTesting ......................... 90

D Berlekamp’sAlgorithm ................................. 95

15 InteractiveProofs...................................... 99

16 PSPACE ⊆ IP ....................................... 103

17 IP ⊆ PSPACE ....................................... 109

18 Probabilistically Checkable Proofs . . . . . . . . . . . . . . . . . . . . . . 113

19 NP ⊆ PCP (n

, 1) .................................... 119

xii Contents

20 More on PCP ........................................ 124

E ACrash Coursein Logic............................... 128

21 Complexity ofDecidable Theories....................... 135

22 Complexity oftheTheory ofReal Addition .............. 140

23 LowerBound for the TheoryofRealAddition ............ 146

24 LowerBoundforIntegerAddition....................... 151

25 Automata on Inﬁnite Strings and S1S ................... 154

26 Determinization of ω-Automata......................... 161

27 Safra’sConstruction................................... 167

28 Relativized Complexity ................................ 171

29 Nonexistence ofSparseComplete Sets ................... 175

F Unique Satisﬁability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

G Toda’sTheorem ...................................... 185

30 Circuit Lower Bounds and Relativized PSPACE = PH .... 192

31 Lower Bounds for Constant Depth Circuits . . . . . . . . . . . . . . . 198

H The Switching Lemma................................. 204

I Tail Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

32 TheGapTheoremandOtherPathology ................. 215

33 Partial Recursive Functions and G¨odel Numberings . . . . . . . 220

34 ApplicationsoftheRecursionTheorem .................. 226

J AbstractComplexity .................................. 231

35 The Arithmetic Hierarchy.............................. 236

36 Complete ProblemsintheArithmetic Hierarchy .......... 242

37 Post’sProblem ....................................... 247

38 TheFriedberg–MuchnikTheorem....................... 253

39 The AnalyticHierarchy................................ 257

40 Kleene’sTheorem..................................... 263

41 FairTerminationandHarel’sTheorem .................. 267

Exercises 273

Homework1 .............................................. 275

Homework2 .............................................. 276

Homework3 .............................................. 277

Homework4 .............................................. 279

Homework5 .............................................. 280

Homework6 .............................................. 281

Homework7 .............................................. 282

Homework8 .............................................. 283

Homework9 .............................................. 284

Homework10 ............................................. 285

Homework11 ............................................. 286

Homework12 ............................................. 287

MiscellaneousExercises .................................... 289