Decidability and halting problem:

Definition of decidability, examples of decidable languages, decidability and recognisability, halting problem, diagonalization, an example of an unrecognizable language.

Decidability and halting problem:

Definition of decidability, examples of decidable languages, decidability and recognisability, halting problem, diagonalization, an example of an unrecognizable language.

Reductions; further undecidable problems:

Different types of reductions. Examples of undecidable problems from formal language theory. Introduction to descriptive complexity theory.

Cook-Levin’s theorem:

The proof of Cook-Levin Theorem. Reduction from SAT to 3SAT.

Time complexity; classes P and NP:

Time complexity classes, definitions of classes P and NP, examples of problems in P and NP, NP-completeness, polynomial-time reductions, extended Church-Turing thesis.

Further NP-complete problems:

NP-completeness proofs for combinatorial optimization problems, such as Vertex Cover, Independent Set, Clique, Traveling Salesman, Knapsack, etc.

Polynomial hierarchy:

Time and space hierarchy theorems. Oracles. Alternating Turing machines. Polynomial-time hierarchy. Examples of complete problems for various levels of hierarchy.

Space complexity:

Definition of the classes L, NL and PSPACE. Relationship between time and space complexity. Savitch’s theorem. Proof that NL=coNL. Examples of PSPACE-complete and NL-complete problems.

Approximation complexity:

Definition of the approximation ratio and approximation algorithms. Complexity class APX. Examples of approximation algorithms for NP-hard optimization problems.

Randomized algorithms and interactive proofs:

Probabilistic Turing machines. Classes BPP, RP, ZPP. Interactive proofs. Arthur-Merlin games; Graph non-isomorphism. IP=PSPACE. PCP theorem: statement and proof ideas.

Complexity of counting: #P

-The class #P. The proof that Permanent is #P- complete. Further examples of hard counting problems. Approximate solutions to hard counting problems. Satisfiability with unique solutions.

Communication complexity:

Definition of communication complexity. Methods of proving lower bounds: fooling set and other approaches. Applications: equality, disjointness, parity, inner product.

Finite automata and regular languages:

Definition of a finite automaton, formal languages, examples of languages that can be recognized by a finite automaton, regular languages, closure under regular operations.

Non-determinism; equivalence between regular expressions and NFA:

Definition of a non-deterministic finite automaton, examples of languages that can be recognized by a non-deterministic finite automaton, equivalence between DFA and NFA, regular expressions, pumping lemma.

Turing machines:

Definition of a Turing machine, examples of Turing machines, non-determinism, Church-Turing thesis, equivalence of different variants of Turing machines.

Pushdown automata and context-free grammars:

Definitions of context-free grammars and pushdown automata, examples, equivalence between context-free languages and languages recognizable by PDA, pumping lemma for PDA, role of determinism.