# Computability & Complexity

Honours Course in Mathematics of Computer Science.

## Lecturer

Vasco Brattka

Department of Mathematics & Applied Mathematics
University of Cape Town

## Time Table (2007)

Lectures for this module take place from
• 14:00-15:45 (period 6 and 7) on Wednesdays and from
• 13:00-14:45 (period M and 6) on Fridays in room M111 (Seminar Room).
The last period on Fridays will be used as tutorial.

## Course Description

Computability and complexity theory are two basic areas of mathematics and computer science and the main goal of these disciplines is to understand up to which extend problems can be solved algorithmically. While algorithms have been implicitly studied since ancient times (Euclid's algorithm is an example), it is only since the seminal work of Turing, Gödel and others that there is a precise notion of an algorithm. Applying this precise notion it turns out that certain problems are not solvable algorithmically in principle (for instance, there is no general method to decide whether two programs do the same job). Other problems turn out to be unsolvable for more practical reasons (there is no known feasible method to check whether a propositional formula is satisfiable). It is computability and complexity theory which studies the underlying mathematical structures behind such problems.

During this course we are going to address, among others, the following topics:

• Models of computability (Turing machines and others)
• Church's thesis
• Recursive and recursively enumerable sets
• Universal Turing machines and Gödel numberings
• Reducibility and simple sets
• Arithmetical hierarchy
• Turing reducibility and Post's problem
• Gödel's Incompleteness Theorem
• Applications to logic
• Complexity measures (time and space)
• The "P=NP?" problem
• Cook's Theorem and NP-complete problems
• The Polynomial-Time Hierarchy
• Polynomial-Time Turing Reducibility

"Universal Turing Machine" © 2003 Jin Wicked, USA.

## Contents

### Part A: Computability

1. Introduction
• Introduction
• Hilbert's Tenth Problem
• The Theorem of Davis, Robinson and Matiyasevich
• The Theorem of Manders and Adleman
• Computability and complexity
• Register machines
2. Computable Functions
• Computable functions
• Terminology for partial functions
• Generalized register machines
• Closure schemes for computable functions
3. Recursive Functions
• Recursive and primitive recursive functions
• Cantor's diagonal method
4. Computability on Natural Numbers and Other Sets
• Klenee's Normalform Theorem
• Church's Thesis
• Numberings
5. Gödel Numberings
• Gödel numbering of computable functions
• Universal machines and Turing's utm-Theorem
6. Effective Programming
• Effective programming and Kleene's smn-Theorem
• Rogers Equivalence Theorem
7. The Recursion Theorem
• The Fixpoint Theorem
• Selfreproducibility
• The Complexity Theorem
• Diagonalization
8. Computable Sets
• Recursive and recursively enumerable sets
• Characterizations
• The Projection Theorem
• The Complementation Theorem
9. The Halting Problem
• The Selfapplicability Problem
• Closure Properties
• The Graph Theorem
• Reducibility
• The Halting Problem
10. Index Sets
• Characterization of r.e. sets by reducibility
• Recursive and r.e. sets with respect to numberings
• Index sets
• The Theorem of Rice
• The Theorem of Myhill and Shepherdson
• The Correctness Problem
• The Equivalence Problem
11. Productive and Creative Sets
• Post's Problem
• Completeness
• Productive and Creative Sets
• Myhill's Characterization of Creativity
12. Immune Sets and Simple Sets
• Immune Sets and Simple Sets
13. Kolmogorov Complexity
• Kolmogorov Complexity
• Random numbers and Lawful Numbers
• Many-one Degrees
• The Lattice of R.e. Sets
• Mezoic Sets
14. Gödel's Incompleteness Theorem
• First Order Arithmetic
• Arithmetical Sets and Functions
• Gödel's Sequence Number Theorem
• Productivity of Arithmetic Truth
• Gödel's Incompleteness Theorem
• Chaitin's Incompleteness Theorem
15. Hilbert's Tenth Problem
• Diophantine Sets and Functions
• A Number Theoretic Characterization of Computability
• The Theorem of Davis, Robinson and Matyasevich
• Hilbert's Tenth Problem
• Davis' Incompleteness Theorem
16. Turing Reducibility
• Oracle Machines
• Relativized Computability
• Turing Reducibility
17. Post's Problem
• The Theorem of Kleene-Post
• Post's Problem for Turing Reducibility
18. The Theorem of Friedberg-Muchnik
• The Theorem of Friedberg-Muchnik
19. The Jump
• The Jump
• The Jump on Degrees
• The Jump Theorem
20. The Arithmetical Hierarchy
• The Arithmetical Hierarchy
• The Theorem of Kuratowski and Tarski
• The Theorem of Post

### Part B: Complexity

1. Computability on Words
• Turing Machines
• Computable Word Functions
• R.e. and Recursive Languages
2. Time and Space Complexity Classes
• Deterministic Time and Space Complexity
• Relation between Time and Space Complexity
3. Tape Reduction
• Complexity of Tape Reduction
• The Crossing Sequence Method and Lower Bounds
4. Time and Space Hierarchy Theorems
• Normed Turing Machines
• Universal Turing Machines
• Time and Space Hierarchy Theorems
5. Nondeterministic Complexity Classes
• Nondeterministic Turing Machines
• Nondeterministic Complexity Classes
• Relation between Nondeterministic and Deterministic Classes
6. Theorem of Savitch and Theorem of Immerman and Szlepcsényi
• Tape Reduction for Nondeterministic Classes
• Theorem of Savitch
• Theorem of Immerman and Szlepcsényi
7. NP-Completeness
• The Polynomial Time Projection Theorem
• Complexity Classes of Functions
• Reducibilities
• NP-Completeness
8. The Theorem of Cook
• The Satisfiability Problem
• The Theorem of Cook
9. NP-Complete Problems
• Graphs, Properties and Encoding
• The Vertex Cover Problem
• The Independent Set Problem
• The Clique Problem
• Other NP-Complete Problems
• The Theorem of Manders and Adleman
10. Oracle Complexity Classes
• Oracle Turing Machines
• Oracle Complexity Classes
11. Polynomial-Time Turing Reducibility
• Polynomial-Time Turing Reducibility
• Optimization Problems
12. The Polynomial-Time Version of the Theorem of Friedberg-Muchnik
• Polynomial-Time Turing Reducibility
• Optimization Problems
• Post's Problem for Polynomial-Time Computability
• The Method of Delayed Diagonalization
• The Polynomial-Time Version of the Theorem of Friedberg-Muchnik
13. The Polynomial-Time Hierarchy
• The Polynomial-Time Hierarchy
• The Hierarchy Theorem
• Polynomial-Time Version of the Kuratowski-Tarski Theorem
14. PSPACE-Completeness
• The Relativized Bounded Halting Problem
• The Relativized Theorem of Cook
• PSPACE-Completeness
15. The Relativized P-NP Problem
• The Relativized P-NP Problem
• The Independence Theorem of Hartmanis and Hopcroft
16. The P-NP Problem with Random Oracles
• Kolmogorov's Zero-One Law
• The Theorem of Benett and Gill on Random Oracles

## Slides

The course slides simultaneously serve as lecture notes.

## Tutorial Sheets (2007)

Here are the tutorial sheets for 2007 together with the deadlines when the solutions have to be handed in:

## References

The following text books are not prescribed to the course but recommended for further reading:
• S. Barry Cooper, Computability Theory, Chapman & Hall, Boca Raton, 2004
Errata (on author's homepage)
(in particular: Chapters 1-10 and parts of Chapters 11 and 12)
• Ding-Zhu Du and Ker-I Ko, Theory of Computational Complexity, John Wiley & Sons, New York 2000
Errata (on author's homepage)
(in particular: Chapters 1-4 and 8)