Introduction to the Theory of Computation

Cover
Statement
	Title Page
Copyright
Dedication
Contents
Preface to the First Edition
Preface to the Second Edition
Preface to the Third Edition
Ch 0: Introduction
	0.1 Automata, Computability, and Complexity
	0.2 Mathematical Notions and Terminology
	0.3 Definitions, Theorems, and Proofs
	0.4 Types of Proof
	Exercises
	Problems
	Selected Solutions
Part 1: Automata and Languages
	Ch 1: Regular Languages
		Introduction
		1.1 Finite Automata
		1.2 Nondeterminism
		1.3 Regular Expressions
		1.4 Nonregular Languages
		Exercises
		Problems
		Selected Solutions
	Ch 2: Context-Free Languages
		Introduction
		2.1 Context-Free Grammars
		2.2 Pushdown Automata
		2.3 Non-Context-Free Languages
		2.4 Deterministic Context-Free Languages
		Exercises
		Problems
		Selected Solutions
Part 2: Computability Theory
	Ch 3: The Church–Turing Thesis
		Introduction
		3.1 Turing Machines
		3.2 Variants of Turing Machines
		3.3 The Definition of Algorithm
		Exercises
		Problems
		Selected Solutions
	Ch 4: Decidability
		Introduction
		4.1 Decidable Languages
		4.2 Undecidability
		Exercises
		Problems
		Selected Solutions
	Ch 5: Reducibility
		Introduction
		5.1 Undecidable Problems From Language Theory
		5.2 A Simple Undecidable Problem
		5.3 Mapping Reducibility
		Exercises
		Problems
		Selected Solutions
	Ch 6: Advanced Topics in Computability Theory
		Introduction
		6.1 The Recursion Theorem
		6.2 Decidability of logical theories
		6.3 Turing Reducibility
		6.4 A Definition of Information
		Exercises
		Problems
		Selected Solutions
Part 3: Complexity Theory
	Ch 7: Time Complexity
		Introduction
		7.1 Measuring Complexity
		7.2 The Class P
		7.3 The Class NP
		7.4 NP-completeness
		7.5 Additional NP-complete Problems
		Exercises
		Problems
		Selected Solutions
	Ch 8: Space Complexity
		Introduction
		8.1 Savitch’s Theorem
		8.2 The Class PSPACE
		8.3 PSPACE-completeness
		8.4 The Classes L and NL
		8.5 NL-completeness
		8.6 NL equals coNL
		Exercises
		Problems
		Selected Solutions
	Ch 9: Intractability
		Introduction
		9.1 Hierarchy Theorems
		9.2 Relativization
		9.3 Circuit Complexity
		Exercises
		Problems
		Selected Solutions
	Ch 10: Advanced Topics in Complexity Theory
		Introduction
		10.1 Approximation Algorithms
		10.2 Probabilistic Algorithms
		10.3 Alternation
		10.4 Interactive Proof Systems
		10.5 Parallel Computation
		10.6 Cryptography
		Exercises
		Problems
		Selected Solutions
Selected Bibliography
Index