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
12
B
ING-INF/05
6
B
ING-INF/05
6
B
ING-INF/05

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

ModulesCreditsTAFSSD
6
B
INF/01
Altre attivita' formative
4
F
-
ModulesCreditsTAFSSD
12
B
ING-INF/05
12
B
ING-INF/05
6
B
ING-INF/05
6
B
ING-INF/05
activated in the A.Y. 2011/2012
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

6

Language

Italian

Scientific Disciplinary Sector (SSD)

ING-INF/05 - INFORMATION PROCESSING SYSTEMS

Period

I semestre dal Oct 4, 2010 al Jan 31, 2011.

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

Learning outcomes

In this courses, the relevant notions in complexity theory are introduced. Main themes are the relationship between complexity classes and Np-completeness theory. The scope of the courses is to give formal instruments useful in the analysis of the difficulty of computational problems.

Program

This is a condensed version of the program. The detailed program (with useful notes for the students) is available in the pdf file "Diario delle Lezioni"

1)Introduction
Computational models, computational resources, tractable problems and feasible algorithms.



2) Computational models and time complexity classes
Deterministic Turing Machine with 1 and k strings
Class TIME(f(n)).
Relationship between k-MdT e 1-MdT (theorem).
Random Access Machine. 

Simulation theorems TM-RAM. 

Thesis of sequential calculus.
Linear speed-up theorem and consequences.
The class P.

Examples of problems in P.


Non deterministic Turing machine(NTM).

Class NTIME(f(n)).

Relationship between NTM and TM.

The class NP.

Examples of problems in NP.
Characterization of problem in NP with polynomial verifier.
The class EXP.



4)Space complexity
.
Input-output TM.
Classes SPACE(f(n)) and NSPACE(f(n)).

Compression Theorem
Classes L e NL.

Examples of problems in L and NL.

Relationship between space and time onf I/O TM

5)Relationship between complexity classes
Proper function.
The reachability method.
Theorems: inclusions between time and space classes. Universal TM.
Lemmata for Time Hierarchy Theorem.

Time Hierarchy Theorem. Corollary P ⊂ EXP.

Space Hierarchy Theorem. Corollary L ⊂ PSPACE.
Gap's Theorem.

Savitch's Theorem with Corollary. Corollary PSPACE=NPSPACE.



6)Reduction and completeness
Reduction and logarithmic reduction.

Examples of reduction: HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.

Examples of reduction by generalization.
Property of reduction: reflexivity and transitivity.
 C-Completeness for a language.

Closure of a class C with respect to reduction.
L, NL, P, NP, PSPACE and EXP are closed w.r.t ≤log.

Table method. Computational table
CIRCUIT VALUE is P-complete.

Cook's theorem.

Examples of NP-complete problems.

7)Some notions on the complement of non deterministic classes
coC
NP and coNP

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

Examination Methods

Written test with open questions.

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

Teaching materials e documents