NTIN090 - Introduction to Complexity and Computability

Petr Kučera, KTIML MFF UK

Winter semester 2018/2019

Petr Kučera

Contents

  1. Links and documents
  2. Exam
  3. Credit
  4. Contents of the lecture
  5. Contents of the practicals

Links and documents

Exam

Exam starts with a written test (usually) at 9:00. The test consists of 3 exercises which are similar to those which you were solving during practicals. Time limit is 60 minutes. The test is followed by an oral part which consists of two questions from the list. There are two possibilities, either one of the questions comes from group A and the other from group D, or one of the questions comes from grou B and the other from group C. Grade is determined based on both the written and oral part.

Credit

Practical is being teached by Dr.Petr Gregor.

Contents of the lecture

1st lecture (4th October, 2018)

Slides 1-41. Motivational example. Definition of Turing machines, equivalence of $k$-tape and $1$-tape Turing machines.

2nd lecture (11th October, 2018)

Slides 42-63. RAM and its equivalence with Turing machines. Encoding Turing machines, Gödel number.

3rd lecture (18th October, 2018)

Slides 64-74. Universal Turing machine. Basic properties of decidable and partially decidable languages, Post's theorem. Diagonalization language is not partially decidable. Language of the Universal Turing machine and the Halting problem are partially decidable, but not decidable.

4th lecture (25th October, 2018)

Slides 75-86. Algorithmically computable functions. Equivalent definitions of partially decidable and decidable languages. Enumerating languages. Definition of \(m\)-reducibility a \(m\)-completeness, and their basic properties.

5th lecture (1st November, 2018)

Slides 87-90. \(m\)-completeness of the language of universal mathine \(L_u\), the Halting problem \(\mathrm{HALT}\), and its diagonal \(K\). Rice's theorem. Post Correspondence Problem (proof not fully finished).

6th lecture (8th November, 2018)

Slides 90-99. Finished the proof of undecidability of the Post Correspondence Problem. Basic complexity classes. Class P.

7th lecture (15th November, 2018)

Slides 100-109. Verifiers and class NP. Nondeterministic Turing machines, alternative definition of class NP with the proof of equivalence. Theorem about relation of time and space.

8th lecture (29th November, 2018)

Slides 109-115. Relations between classes. Savitch's theorem. Space hierarchy theorem.

9th lecture (6th December, 2018)

Slides 116-120. Time hierarchy theorem. Polynomial reducibility and NP-completeness.

10th lecture (13th December, 2018)

Slides 121-122. NP-completeness of Tiling, Satisfiability (Cook-Levin Theorem).

11th lecture (20th December, 2018)

Slides 123-131. NP-completeness of 3-Satisfiability, Vertex Cover, and Partition. Other NP-complete problems mentioned without proof.

12th lecture (3rd January, 2019)

Slides 129-148. Finished proof of NP-completeness of Partition. Pseudopolynomial algorithm for Knapsack. Pseudopolynomial algorithms and strongly NP-complete problems (definitions). Strong NP-completeness of Travelling Salesperson. Approximation algorithms for Bin Packing.

13th lecture (10th January, 2019)

Slides 149-158. Inapproximability of Travelling salesperson. Fully polynomial time approximation scheme for Knapsack (proof only sketched). Connection of FPTAS to strong NP-completeness. Class co-NP and co-NP completeness.