comp3 — Computability and Computational Complexity
Academic year 2018-2019,
CS Master degree at the University of Trento, Italy.

Basic information

Important news

The text and the answer outlines of the July 22 exam are published below.


Fall semester, four hours a week, for a minimum of 48 hours.

The 2018 edition is over.


Mauro Brunato <>

Please email me if you want to set up a meeting.

Course description

Aim of the course

The course sets the theoretical bases for being able to discuss two fundamental properties of computational problems.

Given a problem, we will initially be concerned about its computability:

  • Is there a method to solve the problem?
  • Can we describe this method in an unequivocal way?
  • Is there a universal “language” for such task?

When a problem is found out to be solvable, we can wonder how efficiently it can be done.

  • What are the meaningful criteria to express how hard a problem is?
  • Is there a meaningful way to classify problems with respect to their hardness?
  • Does this classification tell us something about the limits of our capability to solve problems?


Basic notions of mathematical logic

Expected outcome

At the end of the course, the students will be able to:

  • Describe problems and problem instances in a formally precise way.
  • Describe the solution of simple problems in terms of a universal computational model (the Turing Machine).
  • Prove that a specific problem (Turing's halting problem) is not computable.
  • Apply the formal notion of reduction in order to extend properties of known problems to new ones.
  • Identify quantitative criteria to describe the complexity of an algorithm with respect to instance size.
  • Describe the main time and space complexity classes, and their inclusion relationships.
  • Define what it means for a problem to be complete for a class.
  • Prove that a specific problem ( SATISFIABILITY) is complete in the NP class (Cook's Theorem).
  • Discuss the P vs. NP problem and its main implications on various branches of computer science.
  • Analyze how extensions of the basic computing model (randomness, quantum computing) can benefit the solution of some problem classes.

Program outline

For the actual program, see below.

  • Computability
    • Turing machines.
    • Decidable languages and computable functions.
    • The Halting Problem.
    • Other undecidable languages and uncomputable functions.
  • Computational Complexity
    • Problem instance size, measures of complexity, classification of problems.
    • Time complexity classes: P, NP, NP-completeness. Study of NP-complete problems.
    • Space complexity classes: LOGSPACE, NLOGSPACE, PSPACE, NPSPACE. Savitch's theorem.
    • Random complexity classes.
    • Advanced topics, depending on available time (interactive proofs, cryptography, quantum computation, approximation).


The following books may be useful, but none is mandatory. References to online material will be provided in the course program section.

Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 9780521424264 [Draft of the book]

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Pearson new International Edition, 2013. ISBN: 9781292039053

Christos H. Papadimitriou. Computational complexity. Addison Wesley (Pearson College Div.), 1994. ISBN 9780020153085

Course material

Lecture notes

Example code

External links

(See the lecture notes for details)


The exam consists of a written test, with exercises and theoretical questions. Examples will be provided in due time in the lecture notes. The “Computability” part will account for about 1/3rd of the final mark, “Computational Complexity” for the remaining 2/3rds.

Exam dates:

  • Monday, June 17, 3pm-6pm, room A106
  • Monday, July 22, 3pm-6pm, room A106
  • Wednesday, September 4, 9.30am-12.30pm, room A106

Past exams

Partial tests

During the course, there were two partial tests, the first on the Computability part, the second on Complexity. Only students passing the first partial test with a minimum 15/30 mark were admitted to the second one.

Students passing both partial tests with a minimum 15/30 mark received the weighted average of their partial marks (Complexity weighs twice) as their final course mark.

Course program


  • Friday, september 14
    • Sets and decision functions; recursive and recursively enumerable sets
    • Informal definitions and examples
  • Tuesday, september 18
    • Turing machines: definitions and examples
    • k-tape Turing machines, equivalence to 1-tape machines.
  • Friday, september 21
    • Size of a TM's alphabet: emulation by a 2-symbol machine
    • Universal Turing machines: encoding a TM on a string.
    • Emulating a CPU with a TM (hints).
    • Correspondence between TMs and decision problems (to be continued).
  • Tuesday, september 25
    • Uncomputable functions: the halting problem
    • The Busy Beaver game
  • Friday, september 28
    • Consequences of uncomputability of the halting problem for mathematics
    • Halting problem for machines with no input
    • Recursive enumerability and co-recursive enumerability
  • Tuesday, october 2
    • Discussion about questions and exercises for the partial test
  • Friday, october 5
    • Semantic properties of Turing machines, Rice's theorem
    • Growth of the Busy Beaver function Σ(n)
  • Tuesday, october 9
    • Discussion about questions and exercises for the partial test

Computational complexity

  • Tuesday, october 16
    • Introduction to computational complexity
    • Class DTIME(f), class P of polynomial-time languages.
    • Examples of languages in P
  • Friday, october 19
    • The class NP.
    • Non-deterministic Turing machines.
    • Examples of languages in NP.
    • Polynomial-time reductions.
  • Tuesday, october 23
    • Sample reductions between NP languages: SATISFIABILITY, INDEPENDENT SET, 3-SATISFIABILITY.
  • Friday, october 26
    • NP-hardness and NP-completeness.
    • Relationship between Boolean circuits and CNF formulas.
    • Representation of a polynomial-time TM computation as a Boolean circuit (to be continued).
  • Tuesday, november 6
    • Representation of a polynomial-time TM computation as a Boolean circuit (continued).
    • Cook's theorem: SAT is NP-complete.
  • Friday, november 9
    • Reductions and proofs of NP-completeness.
  • Tuesday, november 13
    • Reductions and proofs of NP-completeness.
    • Classes EXP and NEXP, relationship with polynomial classes.
  • Friday, november 16
    • Randomized complexity classes: the class RP.
  • Tuesday, november 20
    • Randomized complexity classes: the Polynomial Identity Testing problem (PIT);
    • the classes ZPP, BPP and PP and their relationships.
  • Friday, november 23
    • Space complexity classes: basic definitions.
    • The classes L, NL, PSPACE, NPSPACE.
  • Tuesday, november 27
    • Space complexity classes: Savitch's theorem.
  • Friday, november 30
    • Functional complexity classes: FP and FNP.
    • Interactive proofs (to be continued).
  • Tuesday, december 4
    • Interactive proofs: the class IP.
  • Friday, december 7
    • Interactive proofs: the class AM[k].
    • NP-complete languages: SUBSET SUM, KNAPSACK.
    • The Merkle-Hellman Knapsack cryptosystem (to be continued).
  • Tuesday, december 11
    • The Merkle-Hellman Knapsack cryptosystem.
    • Zero-knowledge proofs.
    • Final remarks: other research directions.