To show the organization of the course that includes this module, follow this link Course organization
|Monday||2:30 PM - 4:30 PM||lesson||Lecture Hall I|
|Tuesday||2:30 PM - 4:30 PM||lesson||Lecture Hall I|
|Thursday||9:30 AM - 10:30 AM||lesson||Lecture Hall I|
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.
Computational model concept, computational resource, efficient algorithm and tractable problem.
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 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 concept. MdT 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 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))).
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.
Randomized computational complexity.
Probabilistic Turing machines.
Computational classes: BPP, RP, coRP e ZPP. Relationship between BPP and other classes.
Approximation algorithms and approximate complexity classes.
|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||principale|
The examination consists of a written test. The grade in this module is worth 1/3 of the grade in the Algorithms examination.