Computability and Complexity. Foundations and Tools for Pursuing Scientific Applications

Preface
Acknowledgements
Introduction
Contents
Part I Background
	Chapter 1
Some Naive Set Theory
		1.1
Introduction
			1.1.1
Basic definitions
			1.1.2
Countable sets
		1.2
Gödel numberings and other coding techniques
			1.2.1
Exercises
		1.3
Diagonalization and Uncountable Sets
			1.3.1 Exercises
		1.4
Set Theory in Mathematics
			1.4.1
The Cardinality of a Set and the Continuum Hypothesis*
Part II Computability Theory
	Chapter
2 Regular Languages and Finite Automata
		2.1
Introduction
		2.2
Regular Languages
			2.2.1
Formal languages
			2.2.2
Regular expressions and languages
			2.2.3
The Pumping Lemma
			2.2.4
Exercises
			2.2.5
Closure properties of regular languages
		2.3
Finite State Automata
			2.3.1
Deterministic Finite Automata
		2.4
Exercises
			2.4.1
Nondeterministic Finite Automata
			2.4.2
The Rabin-Scott Theorem
			2.4.3
Exercises
			2.4.4 Nondeterministic automata with ⋋-moves
		2.5
Exercises
		2.6
Kleene\'s Theorem: Finite State = Regular
			2.6.1
Historical Notes
		2.7
The Myhill-Nerode Theorem*
			2.7.1
The Method of Test Sets
			2.7.2
State Minimization*
			2.7.3
Exercises
			2.7.4
Historical Notes
	Chapter
3 General Models of Computation
		3.1
Introduction
		3.2
Turing Machines
			3.2.1
Exercises
			3.2.2
Coding, Gödel numbering and other domains beside N
			3.2.3
 Exercises
			3.2.4
The Church-Turing Thesis
			3.2.5
Nondeterminism
			3.2.6
A Universal Turing machine
		3.3
Partial recursive functions
			3.3.1
Primitive recursive functions
			3.3.2
Exercises
			3.3.3
Primitive Recursive Relations
			3.3.4
Bounded quantification
			3.3.5
Exercises
			3.3.6
Partial recursive functions
			3.3.7
Gödel Numbering Turing Computations
			3.3.8
The Kleene Normal Form Theorem
		3.4
Minsky and Register Machines
			3.4.1
Exercises
	Chapter 4
Undecidable Problems
		4.1
Introduction
			4.1.1
Exercises
			4.1.2
The Halting Problem
			4.1.3
Exercises
		4.2
Minsky Machines and Generalized Collatz Functions
			4.2.1
Collatz functions
			4.2.2
Vector games
			4.2.3
Rational Games
			4.2.4
Generalized Collatz functions
			4.2.5
Exercises
		4.3
Unsolvable Word problems
			4.3.1
Semi-Thue Processes
			4.3.2
Thue Processes and Word Problems in Semigroups
			4.3.3
Exercises
			4.3.4
Post\'s correspondence problem
			4.3.5 Groups*
			4.3.6
The Entscheidungsproblem*
			4.3.7
Diophantine equations*
			4.3.8
Exercises
			4.3.9
Coda
	Chapter 5
Deeper Computability
		5.1
Introduction
			5.1.1
Computably Enumerable Sets
			5.1.2
Exercises
			5.1.3
The s-m-n Theorem
		5.2
Index Sets and Rice\'s Theorem
		5.3
The Recursion Theorem
			5.3.1
An Alternative Proof of the Recursion Theorem*
			5.3.2
Exercises
		5.4
Wait and See Arguments
			5.4.1
Some Examples
			5.4.2
Computable Structure Theory: Computable Linear Orderings
			5.4.3
Exercises
		5.5
Turing Reducibility
			5.5.1
Oracle machines and Turing reducibility
			5.5.2
Universal Oracle Machines
			5.5.3
Use functions
			5.5.4
The jump operator
		5.6
The Arithmetic Hierarchy
			5.6.1
The Limit Lemma
			5.6.2
Exercises
			5.6.3
Post\'s Theorem
			5.6.4
Exercises
		5.7
The Structure of Turing Degrees and Post\'s Problem
			5.7.1
Exercises
			5.7.2
Post\'s Problem and the Finite Injury Priority Method
			5.7.3
Exercises
			5.7.4
Sacks\' Splitting Theorem*
			5.7.5
Exercises
Part III Computational Complexity Theory
	Chapter 6
Computational Complexity
		6.1
Introduction
			6.1.1
Size matters
			6.1.2
The Basic Model
			6.1.3
Discussion and Basic Definitions
			6.1.4
Exercises
			6.1.5
Polynomial Time and Space
			6.1.6
Universal Enumerations
			6.1.7
Using Clocks
			6.1.8
Hierarchy Theorems
			6.1.9
Exercises
		6.2
Blum\'s Speedup Theorem
		6.3
The Union Theorem*
	Chapter 7
NP- and PSPACE-Completeness
		7.1
The Polynomial Time Hierarchy
		7.2
NP Completeness
			7.2.1
Machine NP-Complete Problems
			7.2.2
Exercises
			7.2.3
The Cook-Levin Theorem
			7.2.4
Search vs Decision Problems: Polynomial Time Turing Reductions
			7.2.5
Exercises
			7.2.6
Some Natural NP-Complete Problems
			7.2.7
Exercises
			7.2.8
More NP-Completeness
			7.2.9
Exercises
			7.2.10
Even More NP-Completeness
			7.2.11
Commentary*
			7.2.12
Exercises
		7.3
Space
			7.3.1
Savitch\'s Theorem
			7.3.2
Time vs Space
			7.3.3
Exercises
		7.4
Natural PSPACE-Complete Problems
			7.4.1 Exercises
		7.5
Further Variations on the Theme : Advice Classes and Randomized Reductions
			7.5.1
Introduction
			7.5.2
Advice and Nonuniform Complexity Classes
			7.5.3
Valiant-Vazirani and BPP
	Chapter 8
Some Structural Complexity
		8.1
Introduction
			8.1.1
Oracles
			8.1.2
Exercises
			8.1.3
The Role of Oracles and Other Indications that We Don\'t Know How to Approach P vs NP
		8.2
Polynomial Time Degrees and Ladner\'s Theorem
			8.2.1
Exercises
	Chapter 9
Parameterized Complexity
		9.1
Introduction
		9.2
Formal Definitions
			9.2.1
Discussion
		9.3
Parametric Intractability
			9.3.1
A basic hardness class: W[1]
			9.3.2
Exercises
			9.3.3
The W-hierarchy
			9.3.4
Showing Known Algorithms are Likely Very Bad Indeed; Especially in PTAS\'s
		9.4
Parameterized Tractability
			9.4.1
Bounded Search Trees
			9.4.2
Exercises
			9.4.3
Kernelization
			9.4.4
Exercises
			9.4.5
Iterative Compression
			9.4.6
Exercises
			9.4.7
Not-Quite-Practical FPT Algorithms*
			9.4.8
Exercises
		9.5
Kernelization Lower Bounds
			9.5.1
Exercises
		9.6
Another Basic Hardness Class and XP Optimality*
			9.6.1
Exercises
	Chapter 10
Other Approaches to Coping with Hardness*
		10.1
Introduction
		10.2
Approximation Algorithms
			10.2.1
Constant Distance Approximation
			10.2.2
Exercises
			10.2.3
Constant Approximation Ratios
			10.2.4
APX Completeness
			10.2.5
Exercises
			10.2.6
PTAS\'s
			10.2.7
Parameterized Approximation
			10.2.8
Parameterized Inapproximability
			10.2.9
Exercises
		10.3
Average Case Complexity
			10.3.1
Polynomial Time on Average
			10.3.2
DistNP
			10.3.3
Livne\'s ``Natural\'\' Average Case Complete Problems
			10.3.4
Exercises
		10.4
Generic Case Complexity
			10.4.1
Basic Definitions
			10.4.2
Exercises
		10.5
Smoothed Analysis
		10.6
Summary
Part IV Selected Solutions to Exercises
	Chapter 11
Solutions
		11.1
Chapter 1
		11.2
Chapter 2
		11.3
Chapter 3
		11.4
Chapter 5
		11.5
Chapter 6
		11.6
Chapter 7
		11.7
Chapter 8
		11.8
Chapter 9
		11.9
Chapter 10
	References
	Index