Computability and Complexity - Seminar

Topics

1. Church's thesis: Register Machines

   Definition of register machines; Theorem that every partical recursive function is computable by a register machine.

   Reference: Klaus Weihrauch: Computability. Springer, 1987.

2. Church's thesis: λ calculus

   (Diogo Sousa)

   Definition of type free λ calculus; Theorem that every partial recursive function is representable in the λ calculus.

   Reference: Henk Barendregt. Lambda Calculi with Types. In S. Abramsky, Dov Gabbay, and T. Maibaum (eds.), Handbook of Logic in Computer Science, Oxford University Press, 1992.

3. Church's thesis: WHILE programs

   Reference: A. J. Kfoury, Robert N. Moll, and Michael A. Arbib. A Programming Approach to Computability, Springer, 1982.

   Definition of WHILE programs; Theorem that every partial recursive function is computable by a WHILE program.

4. Turing machines: Tape reduction

   Definition of k tape Turing machine; Theorem that every function computable with k tape Turing machine is computable with a 1 tape Turing machine (considering also the complexity "costs").

   Reference: José Luis Balcázar, Josep Días, and Joaquim Gabarró. Structural Complexity. Volumes I. Springer, 1988

5. Models of computation: Alternating Turing machines

   Reference: Section 3.2 of José Luis Balcázar, Josep Días, and Joaquim Gabarró. Structural Complexity. Volumes I. Springer, 1988

6. NP-completeness: Hamiltonian circuit

   (João Martins)

   Reduction of Hamiltonian circuit to Vertex cover.

   Reference: Section 3.1.4 of M. R. Garey and D. S. Johnson. Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H.Freeman and Co., San Francisco, 1979.

7. PSPACE-completeness: Quantified Booleans Formulas

   Reference: José Luis Balcázar, Josep Días, and Joaquim Gabarró. Structural Complexity. Volumes I. Springer, 1988

8. NL-completeness: GAP (encoded directed graphs with a path from the first to the last vertex)

   Reference: Section 3.3 of Andrzej Szepietowski. Turing Machines with Sublogarithmic Space. Lecture Notes in Computer Science 843, Springer, 1994.