To show the organization of the course that includes this module, follow this link Course organization
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.
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.).
Computational models, computational resources, efficient algorithms and tractable problems.
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 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 concept. TM with I/O. Computational Classes: SPACE() and NSPACE().
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))).
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.
|Christos H. Papadimitriou||Computational complexity||Addison Wesley||1994||0201530821|
|S. Arora, B. Barak||Computational Complexity. A modern approach (Edizione 1)||Cambridge University Press||2009||9780521424264|
The examination consists of a written test. The grade in this module is worth 1/2 of the grade in the Algorithms examination.