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 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.
All rights reserved. Used by permission. JinWicked.com


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
    • Russel's Paradox
    • 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
    • Berry's Paradox
    • 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
    • Quadratic Diophantine Equations
    • 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: For additional reading the following books might be helpful as well:

History

Here are some links to biographies of some famous mathematicians (at Mathematics Archive St Andrews): An here is a link (offered by James T. Smith, San Francisco): including the corresponding MP3 file.


© 2004-2007 Vasco Brattka