Introduction to Complexity and Computability

Basic information

  • Name: Introduction to Complexity and Computability
  • Code: NTIN090
  • Hours per week, examination: winter semester 2/1 C+Ex
  • Language: English (Czech course)
  • Schedule
  • Year: 2017/18

Colleagues

Lecture

Slides from lectures and their compact version are regularly updated. Slides from my Czech lecture.

Past lectures

1. lecture on 5.10.
  • Introduction
  • Examples of undecidable problems
  • Random access machine and Turing machine
  • Resources: [1, chapter 3], [9, lecture 6]
2. lecture on 12.10.
  • Equivalence of RAM and Turing machine
  • Alphabet, language, undecidable languages (HALT, ACCEPT, EMPTY)
  • Resources: [1, chapter 4], Wikipedia, [9, lecture 7]
3. lecture on 19.10.
  • Equivalence of RAM and Turing machine
  • Post theorem, computable function, universal language, enumerator, reducibility, s-m-n lemma
  • Resources: [1, chapter 4], Wikipedia, [9, lecture 7]
4. lecture on 26.10.
  • Reducibility, Post correspondence problem, Rice theorem
  • Resources: [1, chapter 4], Wikipedia, [9, lecture 7]
5. lecture on 2.11.
  • Time and space complexity, Verifier and Non-deterministic Turing machine, complexity classes
6. lecture on 9.11.
  • Relations between classes, Savitch theorem
7. lecture on 16.11.
  • Time and space hierarchy theorems
no lecture on 23.11.
8. lecture on 30.11.
  • NP-completeness of Tiling and SAT
9. lecture on 7.12.
  • NP-completeness of 3-SAT, Vertex cover, TSP, Subset-Sum
  • Pseudopolynomial algorithm for Sumset-Sum problem
10. lecture on 14.12.
  • Strong NP-completeness and pseudopolynomial algorithms
  • Approximation algorithms for vertex cover and TSP
11. lecture on 21.12.
  • Inapproximability of TSP
  • Fully polynomial approximation schemes
12. lecture on 4.1.
  • Co-NP, #P
13. lecture on 11.1.
  • FPT class and algorithms

Literature

  1. Sipser, M.: Introduction to the Theory of Computation Vol. 2. Boston: Thomson Course Technology, 2006.
  2. Garey, Johnson: Computers and intractability - a guide to the theory of NP-completeness, W.H. Freeman 1978
  3. Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987
  4. Odifreddi P.: Classical recursion theory, North-Holland, 1989
  5. Arora S., Barak B.: Computational Complexity: A Modern Approach. Cambridge University Press 2009.
  6. Erik Demaine, and Srinivas Devadas: Introduction to Algorithms (6.006). MIT OpenCourseWare, Fall 2011. Video lectures
  7. Erik Demaine, Srinivas Devadas, and Nancy Lynch: Design and Analysis of Algorithms (6.046J). MIT OpenCourseWare, Spring 2015. Video lectures
  8. T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Third edition, MIT Press, 2009. On-line
  9. Scott Aaronson. Automata, Computability, and Complexity (6.045J). MIT OpenCourseWare, Spring 2011. Lecture notes
  10. Donald E. Knuth: The art of computer programming. Volume 1, Fundamental algorithms. Addison-Wesley, 1968. Available in our library.
  11. K. Mehlhorn: Data structures and algorithms. 2, Graph algorithms and NP-completeness. Springer, Berlin, 1984. Available in our library.
  12. J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to automata theory, languages, and computation, Addison-Wesley, 2001. Available in our library.
  13. Michael R. Garey, David S. Johnson: Computers and intractability : a guide to the theory of NP-completeness. W. H. Freeman and Company, 1979. Available in our library.
Useful links: Catalogue of our library, access to electronic versions of some librarian's books and list of other databazes.

Prerequisites, Expected knowledge

Computational Complexity
NP-completeness, undecidability, computational models, non-deterministic computation
[6, lecture 23], [7, lectures 1, 16], [1, chapters 1-3], [8, chapter 34], [9, lectures 1-6, 12, 15], [10], [11], [12], [13]

Examination

Student must fulfill the following two conditions to pass this subject.

  • Obtain at least 2/3 of all points from homeworks.
  • Pass the exam (will be specified in the end of the semester). Use SIS to register in an exam term.

Tutorials

Students must obtain at least 100 points to pass. Students having at least 69 points from semestral homeworks can try to solve supplementary problems to get extra points.
DateProblem sheetsProblems for homeworksDeadline
12.10.13, 726. 10.
26.10.26, 79. 11.
9.11.36, 77. 12.
7.12.45, 621. 12.
21.12.58, 911. 1.
11.1.6None

Homeworks

Homeworks will be given during every tutorial in problem sheets. Deadline is the next tutorial. Solutions can be sent by an e-mail in the PDF format (before the tutorial!) or handed a hard-copy in during the tutorial. Solutions can be written by hand but then originals are required (scanned copies are rejected).

Explanations or proves are the essential parts of these theoretical homeworks. Students are expected to learn how to write mathematical proofs.