To show the organization of the course that includes this module, follow this link:  Course organization

Learning outcomes

The goal of this module is to introduce students to computational complexity theory in general, to the NP-completeness theory in detail and to computational analysis of problems with respect to their approximability.

Recommended Prerequisite
------------------------
To attend the course lessons in a productive way, a student should be confident with the following concepts:
1. Basic data structures as list, stack, queue, tree, heap.
2. Graph representation and fundamental graph algorithms:
2.1 Graph visit: BFS, DFS.
2.2 Topological ordering. Connected component.
2.3 Minimal spanning tree. Kruskal and Prim algorithm.
2.4 Single-source shortest path: Dijkstra algorithm and Bellman-Ford one.
2.5 All-pairs shortest path: Floyd-Warshall algorithm and Johnson one.
2.6 Max flow: Ford-Fulkerson algorithm.
A recommended book to revise the above concepts is ``Introduction to Algorithms" di T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein (3 ed.).

Program

Introduction.
Computational model concept, computational resource, efficient algorithm and tractable problem.

Computational models
Turing Machine (MdT): definition, behavior, configuration, production and computation concepts. MdT examples. MdT and languages: the difference between accepting and deciding a language. MdT extension: multi-tape MdT (k-MdT)

Time Complexity
Time computational resource. Computational class TIME(). Theorem about polynomial relation between k-MdT computations and MdT ones (sketch of proof).
Introduction to Random Access Machine (RAM) computational model: configuration, program and computation concepts. RAM: computation time by uniform cost criterion and by logarithmic cost one. Example of a RAM program that determines the product of two integers.
Theorem about simulation cost of a MdT by a RAM.
Theorem about simulation cost of a RAM program by a MdT.
Sequential Computation Thesis and its consequences.
Linear Speed-up Theorem and its consequences.

P Computational Class.
Problems in P: PATH, MAX FLOW, PERFECT MATCHING.

Extension of MdT: non-deterministic MdT (NMdT).
Time resource for k-NMdT. NTIME() computational class.
Example of non-deterministic algorithm computable by a NMdT: algorithm for Satisfiability (SAT).

Relation between MdT and NMdT.

NP Computational Class.
Relation between P and NP. Example of a problem into NP: Travel-salesman Problem (TSP).
An alternative characterization of NP: polynomial verifiers.

EXP Computation Class.

Space Complexity.
Space complexity concept. MdT with I/O. Computational Classes: SPACE() and NSPACE().
Compression Theorem.
Computational Classes: L and NL.
Example of problems: PALINDROME ∈ L and PATH ∈ NL.

Theorems about relations between space and time for a MdT with I/O.
Relations betwee complexity classes.
Proper function concept and example of proper functions.
Borodin Gap Theorem.

Reachability method. Theorem about space-time classes: NTIME(f(n)) ⊆ SPACE(f(n)), NSPACE(f(n)) ⊆ TIME(k(log n+f(n))).

Universal MdT.
The Hf set.
Lemma 1 and 2 for time hierarchy theorem.
Time Hierarchy Theorem: strict and no-strict versions.
P ⊂ EXP Corollary.

Space Hierarchy Theorem. L ⊂ PSPACE Corollary.
Savitch Theorem. SPACE(f(n))=SPACE(f(n)^2) corollary. PSPACE=NPSPACE Corollary.

Reductions and completeness.
Reduction concept and logarithmic space reduction. HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.
Language completeness concept.
Closure concept with respect to reduction.
Class reduction of L, NL, P, NP, PSPACE and EXP.
Computation Table concept.
Theorem about P-completeness of CIRCUIT VALUE problem.
Cook Theorem: an alternative proof.
Gadget concept and completeness proof of: INDEPENDENT SET, CLIQUE, VERTEX COVER and others.

Approximation algorithms and approximate complexity classes.

Examination Methods

The examination consists of a written test. The grade in this module is worth 1/3 of the grade in the Algorithms examination.