comp3 — Computability and Computational Complexity
CS Master degree at the University of Trento, Italy.

## Basic information

[2023-09-05]

#### Schedule

Fall semester, from Monday, September 11 to Tuesday, December 19; four hours per week.

• Mondays: 10:30—12:30, room A107.
• Tuesdays: 13:30—15:30, room A103.

#### Instructor

Mauro Brunato < mauro.brunato@unitn.it>

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?

#### Prerequisites

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 and recognize the importance of this result.
• 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.
• Rice's Theorem.
• Computational Complexity
• Problem instance size, measures of complexity, classification of problems.
• Time complexity classes: P, NP, EXP. NP-completeness. Study of NP-complete problems.
• Space complexity classes: LOGSPACE, NLOGSPACE, PSPACE, NPSPACE. Savitch's theorem.
• Polynomial hierarchy and canonical complete problems.
• Advanced topics, depending on available time ((randomized classes, counting classes, interactive proofs, cryptography, quantum computation, approximation).

#### Textbooks

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

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

, , and . Introduction to Automata Theory, Languages and Computation. Pearson new International Edition, 2013. ISBN: 9781292039053

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

## Course materials

This section will contain course material and exercises.\\ Nota bene — The initial material is based on previous editions of the course, and will likely change during the Semester.

### Lecture notes

• 2023-09-05 version: notes are based on previous iterations of this course; they will be changed during the Semester: please see the included changelog for details.

### Example code

(See the lecture notes for details)

## Exams

The exam consists of a written test, with exercises and theoretical questions. Examples are provided in the lecture notes.

### Past exams

• Exercises from previous years' exams that are compatible with this year's program appear in the lecture notes.
• ## Course program

This Section will be updated during the year.
• 2023-09-11
• Basic definitions: alphabet, string, language. Enumerating strings.
• Enumeration of countable sets, diagonal proofs of uncountability.
• 2019-09-12
• Examples of potentially infinite computations based on some unsolved mathematical conjectures (Goldbach, Collatz).
• Intuitive definitions of recursive and recursively enumerable sets. Diagonal procedure to enumerate R.E. sets.
• Turing machines: intuition, introduction.
• 2023-09-18
• Turing machines; representation of their transition function as a table. Examples.
• 2023-09-19
• Computational power of Turing machines: multiple tapes, alphabet size. Reduction to 1-tape, 2-symbol machines with quadratic time loss.