Studying at the University of Verona

Here you can find information on the organisational aspects of the Programme, lecture timetables, learning activities and useful contact details for your time at the University, from enrolment to graduation.

This information is intended exclusively for students already enrolled in this course.
If you are a new student interested in enrolling, you can find information about the course of study on the course page:

Laurea magistrale in Ingegneria e scienze informatiche - Enrollment from 2025/2026

The Study Plan includes all modules, teaching and learning activities that each student will need to undertake during their time at the University.
Please select your Study Plan based on your enrollment year.

CURRICULUM TIPO:

1° Year 

ModulesCreditsTAFSSD
12
B
ING-INF/05
6
B
ING-INF/05
6
B
ING-INF/05
12
B
ING-INF/05
6
B
ING-INF/05

2° Year   activated in the A.Y. 2010/2011

ModulesCreditsTAFSSD
6
B
INF/01
Altre attivita' formative
4
F
-
ModulesCreditsTAFSSD
12
B
ING-INF/05
6
B
ING-INF/05
6
B
ING-INF/05
12
B
ING-INF/05
6
B
ING-INF/05
activated in the A.Y. 2010/2011
ModulesCreditsTAFSSD
6
B
INF/01
Altre attivita' formative
4
F
-
Modules Credits TAF SSD
Between the years: 1°- 2°

Legend | Type of training activity (TTA)

TAF (Type of Educational Activity) All courses and activities are classified into different types of educational activities, indicated by a letter.




S Placements in companies, public or private institutions and professional associations

Teaching code

4S02709

Credits

4

Language

Italian

Scientific Disciplinary Sector (SSD)

ING-INF/05 - INFORMATION PROCESSING SYSTEMS

Period

1st Semester dal Oct 1, 2009 al Jan 31, 2010.

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.

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.

Reference texts
Author Title Publishing house Year ISBN Notes
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821 testo principale

Examination Methods

The examination consists of a written test (at the same time as the other two module tests) that lasts 1 hour (all tests together last 3 hours). The grade in this module is worth 1/3 of the grade in the Algorithms examination.

Students with disabilities or specific learning disorders (SLD), who intend to request the adaptation of the exam, must follow the instructions given HERE