Insegnamento a.a. 2022-2023


Department of Computing Sciences

Course taught in English
Go to class group/s: 31
CLEAM (6 credits - II sem. - OP  |  INF/01) - CLEF (6 credits - II sem. - OP  |  INF/01) - CLEACC (6 credits - II sem. - OP  |  INF/01) - BESS-CLES (6 credits - II sem. - OP  |  INF/01) - WBB (6 credits - II sem. - OP  |  INF/01) - BIEF (6 credits - II sem. - OP  |  INF/01) - BIEM (6 credits - II sem. - OP  |  INF/01) - BIG (6 credits - II sem. - OP  |  INF/01) - BEMACS (6 credits - II sem. - OP  |  INF/01) - BAI (6 credits - II sem. - OP  |  INF/01)
Course Director:

Classes: 31 (II sem.)
Class 31: ALON ROSEN

Lezioni della classe erogate in presenza

Suggested background knowledge

It is recommended to have previously taken a course on computer programming that covered basic algorithms and to be familiar with basic concepts from discrete mathematics and probability. The course will be mathematically rigorous, and so it is also recommended to have the ability to understand definitions and to follow and synthesize mathematical proofs.

Mission & Content Summary


In this course we will learn how to reason precisely about computation and prove mathematical theorems about its capabilities and limitations. We will start by studying the theory of Computability, which is concerned with the rigorous definition of computational tasks and the analysis of automated procedures that may solve them. This will set the stage for the theory of Computational Complexity, whose goal is to examine what are the resources that are necessary for any algorithm to solve a given task. We will end by discussing cryptography and how it makes use of computational hardness. Topics covered in the course include Turing machines, universality, non-determinism, the halting problem, recursive and recursively enumerable functions, space and time complexity, the classes P and NP, reducibility between decision problems, the Cook-Levin theorem, NP-completeness, encryption and authentication.


Unit 1 (Computability - introduction)

·         Course overview

·         Introduction

·         Turing Machine (TM)


Unit 2 (Computability – more on TM)

·         More on the definition of TM

·         Decidable and Recognizable languages

·         Variants of TM

·         Simulation


Unit 3 (Computability – undecidability)

·         The Church-Turing Thesis

·         Examples of decidable languages

·         The Halting problem


Unit 4 (Computability – undecidability contd.)

·         More non-decidable problems

·         Reductions


Unit 5 (Computability – Rice’s theorem)

·         Rice’s Theorem

·         Post Correspondence Problem

·         Wrap up computability


Unit 6 (Complexity - Introduction)

·         Definition of time complexity

·         Complexity of single vs Multiple Tape TM’s

·         PTIME, PATH


Unit 7 (Complexity – The class NP)

·         Non-deterministic TM

·         Poly-time verifiability

·         The classes NP and coNP


Unit8 (Complexity – NP completeness)

·         Poly-time reducibility

·         NP completeness

·         Existence of NP-complete problems


Unit 9 (Complexity – Cook-Levin)

·         Cook-Levin Theorem

·         More NP-complete problems

·         Decision vs. Search


Unit 10 (Complexity – The class PSPACE)

·         Cook/Karp/Levin reductions

·         Coping with NP-hardness

·         Space complexity


Unit 11 (Cryptography - Encryption)

·         Perfect secrecy

·         Computational secrecy


Unit 12 (Cryptography - Authentication)

·         Message authentication

·         Digital signatures


Intended Learning Outcomes (ILO)


At the end of the course student will be able to...

The most important skill that the students are expected to pick up during this course is the ability to recognize and interpret computational intractability in case it is encountered. The course aims to develop a solid conceptual understanding of notions related to computation:

·         The concept of universal models of computation (such as Turing machines), that capture our intuitive notion of computation and allow us to reason about the capabilities of computers in a technology-independent manner.

·         The existence of intrinsic limits to computation. Computational problems that cannot be solved by any algorithm whatsoever (undecidability), and problems that are solvable but require unreasonable computational resources (computational complexity).

·         The notion of nondeterminism and in particular the conceptual difference between finding a solution and verifying that a given solution is correct.

·         The representation of computational problems, and the distinction/relationships between decision and search problems.

·         The notion of a reduction between computational problems and its implications on the relative complexity of the problems.


At the end of the course student will be able to...
  • Recognize problems that are NP-complete, and be able to devise simple NP-completeness proofs
  • Recognize problems that are  undecidable, and be able to devise simple undecidability proofs
  • Apply the idea of a reduction among computational problems
  • Apply definitions of security in encryption and authentication 
  • Be able to spot potential problems in proposed cryptographic protocols

Teaching methods

  • Face-to-face lectures
  • Online lectures
  • Guest speaker's talks (in class or in distance)


Biweekly homework assignments (4-5 questions each) will give you feedback on how you are doing and will help you internalize the material studied.

Assessment methods

  Continuous assessment Partial exams General exam
  • Written individual exam (traditional/online)
  • Individual assignment (report, exercise, presentation, project work etc.)


Assessment will be the same for attending and non-attending students.
Written exam (70% of the final grade) consists of open-ended questions,
some of which will test the student's understanding of the concepts
developed during the course (for example, the ability to reason about
graphs, to reason about the correctness of a given algorithm, or to analyze
the running time of a given
algorithm) and some of which will test the student's ability to apply such
concepts to new contexts, for example their ability to devise an algorithm
for a new problem, to prove the NP-completeness of a new problem, or to
prove the undecidability of a new problem.

Students can take the first partial written exam in the middle of the
semester and complete the second partial exam at the end of the course. In
this case the weight is: 35% for the first partial exam and 35% for the
second partial exam.
Alternatively, students can take a final written exam that accounts for 70%
of the final grade.


Teaching materials


There is no required textbook. Recommended textbooks will be communicated to the students at the start of classes. Lecture slides and notes will be provided for selected topics.

Last change 23/11/2022 11:56