Introduction To The Theory Of Computation

by Sipser,Michael

• ISBN13: 9780534950972
• ISBN10: 0534950973
• Edition: 2nd
• Format: Hardcover
• Copyright: 2005-02-15
• Publisher: Cengage Learning

Summary

This highly anticipated revision builds upon the strengths of the previous edition. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative "proof idea" sections explain profound concepts in plain English. The new edition incorporates many improvements students and professors have suggested over the years, and offers updated, classroom-tested problem sets at the end of each chapter.

Author Biography

Michael Sipser is the head of the Mathematics Department. He enjoys teaching and pondering the many mysteries of complexity theory

Table of Contents

Preface to the First Edition	xi
To the student	xi
To the educator	xii
The first edition	xiii
Feedback to the author	xiii
Acknowledgments	xiv
Preface to the Second Edition	xvii
Introduction	1	(28)
Automata, Computability, and Complexity	1	(2)
Complexity theory	2	(1)
Computability theory	2	(1)
Automata theory	3	(1)
Mathematical Notions and Terminology	3	(14)
Sets	3	(3)
Sequences and tuples	6	(1)
Functions and relations	7	(3)
Graphs	10	(3)
Strings and languages	13	(1)
Boolean logic	14	(2)
Summary of mathematical terms	16	(1)
Definitions, Theorems, and Proofs	17	(4)
Finding proofs	17	(4)
Types of Proof	21	(8)
Proof by construction	21	(1)
Proof by contradiction	21	(1)
Proof by induction	22	(3)
Exercises, Problems, and Solutions	25	(4)
Part One: Automata and Languages	29	(106)
Regular Languages	31	(68)
Finite Automata	31	(16)
Formal definition of a finite automaton	35	(2)
Examples of finite automata	37	(3)
Formal definition of computation	40	(1)
Designing finite automata	41	(3)
The regular operations	44	(3)
Nondeterminism	47	(16)
Formal definition of a nondeterministic finite automaton	53	(1)
Equivalence of NFAs and DFAs	54	(4)
Closure under the regular operations	58	(5)
Regular Expressions	63	(14)
Formal definition of a regular expression	64	(2)
Equivalence with finite automata	66	(11)
Nonregular Languages	77	(22)
The pumping lemma for regular languages	77	(5)
Exercises, Problems, and Solutions	82	(17)
Context-Free Languages	99	(36)
Context-free Grammars	100	(9)
Formal definition of a context-free grammar	102	(1)
Examples of context-free grammars	103	(1)
Designing context-free grammars	104	(1)
Ambiguity	105	(1)
Chomsky normal form	106	(3)
Pushdown Automata	109	(14)
Formal definition of a pushdown automaton	111	(1)
Examples of pushdown automata	112	(3)
Equivalence with context-free grammars	115	(8)
Non-context-free Languages	123	(12)
The pumping lemma for context-free languages	123	(5)
Exercises, Problems, and Solutions	128	(7)
Part Two: Computability Theory	135	(110)
The Church-Turing Thesis	137	(28)
Turing Machines	137	(11)
Formal definition of a Turing machine	139	(3)
Examples of Turing machines	142	(6)
Variants of Turing Machines	148	(6)
Multitape Turing machines	148	(2)
Nondeterministic Turing machines	150	(2)
Enumerators	152	(1)
Equivalence with other models	153	(1)
The Definition of Algorithm	154	(11)
Hilbert's problems	154	(2)
Terminology for describing Turing machines	156	(3)
Exercises, Problems, and Solutions	159	(6)
Decidability	165	(22)
Decidable Languages	166	(7)
Decidable problems concerning regular languages	166	(4)
Decidable problems concerning context-free languages	170	(3)
The Halting Problem	173	(14)
The diagonalization method	174	(5)
The halting problem is undecidable	179	(2)
A Turing-unrecognizable language	181	(1)
Exercises, Problems, and Solutions	182	(5)
Reducibility	187	(30)
Undecidable Problems from Language Theory	188	(11)
Reductions via computation histories	192	(7)
A Simple Undecidable Problem	199	(7)
Mapping Reducibility	206	(11)
Computable functions	206	(1)
Formal definition of mapping reducibility	207	(4)
Exercises, Problems, and Solutions	211	(6)
Advanced Topics in Computability Theory	217	(28)
The Recursion Theorem	217	(7)
Self-reference	218	(3)
Terminology for the recursion theorem	221	(1)
Applications	222	(2)
Decidability of logical theories	224	(8)
A decidable theory	227	(2)
An undecidable theory	229	(3)
Turing Reducibility	232	(1)
A Definition of Information	233	(12)
Minimal length descriptions	234	(4)
Optimality of the definition	238	(1)
Incompressible strings and randomness	239	(3)
Exercises, Problems, and Solutions	242	(3)
Part Three: Complexity Theory	245	(170)
Time Complexity	247	(56)
Measuring Complexity	247	(9)
Big-O and small-o notation	248	(3)
Analyzing algorithms	251	(3)
Complexity relationships among models	254	(2)
The Class P	256	(8)
Polynomial time	256	(2)
Examples of problems in P	258	(6)
The Class NP	264	(7)
Examples of problems in NP	267	(2)
The P versus NP question	269	(2)
NP-completeness	271	(12)
Polynomial time reducibility	272	(4)
Definition of NP-completeness	276	(1)
The Cook-Levin Theorem	276	(7)
Additional NP-complete Problems	283	(20)
The vertex cover problem	284	(2)
The Hamiltonian path problem	286	(5)
The subset sum problem	291	(3)
Exercises, Problems, and Solutions	294	(9)
Space Complexity	303	(32)
Savitch's Theorem	305	(3)
The Class PSPACE	308	(1)
PSPACE-completeness	309	(11)
The TQBF problem	310	(3)
Winning strategies for games	313	(2)
Generalized geography	315	(5)
The Classes L and NL	320	(3)
NL-completeness	323	(3)
Searching in graphs	325	(1)
NL equals coNL	326	(9)
Exercises, Problems, and Solutions	328	(7)
Intractability	335	(30)
Hierarchy Theorems	336	(12)
Exponential space completeness	343	(5)
Relativization	348	(3)
Limits of the diagonalization method	349	(2)
Circuit Complexity	351	(14)
Exercises, Problems, and Solutions	360	(5)
Advanced topics in complexity theory	365	(50)
Approximation Algorithms	365	(3)
Probabilistic Algorithms	368	(12)
The class BPP	368	(3)
Primality	371	(5)
Read-once branching programs	376	(4)
Alternation	380	(7)
Alternative time and space	381	(5)
The Polynomial time hierarchy	386	(1)
Interactive Proof Systems	387	(12)
Graph nonisomorphism	387	(1)
Definition of the model	388	(2)
IP = PSPACE	390	(9)
Parallel Computation	399	(6)
Uniform Boolean circuits	400	(2)
The class NC	402	(2)
P-completeness	404	(1)
Cryptography	405	(10)
Secret keys	405	(2)
Public-key cryptosystems	407	(1)
One-way functions	407	(2)
Trapdoor functions	409	(2)
Exercises, Problems, and Solutions	411	(4)
Selected Bibliography	415	(6)
Index	421