Algorithms - COMPLESSITÀ (2013/2014)

Learning outcomes

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

Recommended Prerequisites
-------------------------
To attend the course in a productive way, a student should be confident with the following topics:
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 topics is ``Introduction to Algorithms" di T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein (3 ed.).

Introduction.
Computational models, computational resources, efficient algorithms and tractable problems.

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

Time Complexity
Time computational resource. Computational class TIME(). Theorem about polynomial relation between k-TM computations and TM ones (sketch of proof).
Introduction to Random Access Machine (RAM) computational model: configuration, program and computation concepts.
RAM: definition of computation time using uniform cost criterion or logarithmic cost one.
Example of a RAM program that determines the product of two integers.
Theorem about time cost for simulating a TM by a RAM program (sketch of the proof).
Theorem about time cost for simulating a RAM program by a TM (only the thesis).
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 TM: non-deterministic TM (NTM).
Time resource for k-NTM. NTIME() computational class.
Example of non-deterministic algorithm computable by a NTM: algorithm for Satisfiability (SAT).

Relation between TM and NTM.

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. TM 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 TM with I/O.
Relations between 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 TM.
The H_f 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.

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