Computability and Complexity. Foundations and Tools for Pursuing Scientific Applications

✍ Scribed by Rod Downey

• Publisher: Springer
• Year: 2024
• Tongue: English
• Leaves: 361
• Series: Undergraduate Topics in Computer Science
• Category: Library

✦ Table of Contents

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