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

## Basic information

#### Important news

[2023-11-23]
An updated version of the notes is available in the Course materials section (see the included Changelog for details).

[2023-11-14]
The exam schedule has been confirmed, dates can be found in the Exams section.

#### 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-11-23 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.

### Final schedule

First call Second call Monday, January 8 2024, 09:00—12:00 Room A103 Monday, February 19 2024, 09:00—12:00 Room A103

### 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.
• 2023-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.
• 2023-09-25
• Universal Turing machines: string encodings of TMs, simulation of TMs.
• Uncomputable functions: their existence by cardinality argument, proof of uncomputability.
• 2023-09-26
• Uncomputability of the halting problem. Special restricions of the halting problem: machines starting from an empty tape.
• Recursive and recursively enumerable languages: Recursive enumerability of HALT.
• 2023-10-02
• Busy beaver functions and their uncomputability.
• 2023-10-03
• Semantic properties of TMs and Rice's theorem.
• 2023-10-09
• Example of uncomputable problem outside of CS: Post's Correspondence Problem.
• 2023-10-10 — Lesson canceled.
• 2023-10-16
• Post's Correspondence Problem (conclusion).
• Reducibility and Turing reductions.
• 2023-10-17
• Computability of the halting problem for classes of restricted TMs.
• Machines with an infinite number of states.
• 2023-10-23
• Oblivious Turing machines.
• Example of uncomputable problems: Kolmogorov complexity.
• 2023-10-24
• Kolmogorov complexity (conclusion).
• Computational complexity: introductory remarks.
• 2023-10-30
• Time classes: DTIME(f), P. Examples of languages in P: CONNECTIVITY.
• CNF Boolean expressions, SATISFIABILITY (SAT), GRAPH ISOMORPHISM, the Traveling Salesman Problem (TSP).
• 2023-10-31
• Language class NP as polynomially-verifiable languages.
• SAT, GRAPH ISOMORPHISM, TSP as NP languages.
• Non-deterministic Turing Machines: introduction.
• 2023-11-06
• Non-deterministic Turing machines (NDTMs); reformulation of the NP time class in terms on polynomial-time NDTMs.
• Polynomial-time reductions: introduction.
• 2023-11-07
• Polynomial-time reductions between known NP problems: SAT, k-SAT (k≥3), CLIQUE, INDEPENDENT SET (INDSET).
• Definitions of NP-hard and NP-complete problems.
• Boolean circuits: introduction.
• 2023-11-13
• Boolean circuits and their reduction to 3-CNF formulas.
• 2023-11-14
• Polynomial reduction of an NDTM's computation to a Boolean circuit with choice bits.
• Cook-Levin Theorem: 3-SAT is NP-complete.
• 2023-11-20
• More NP languages: VERTEX COVER, INTEGER LINEAR PROGRAMMING (ILP).
• Reductions: INDEPENDENT SET to VERTEX COVER and to ILP.
• 2023-11-21
• More NP languages: VERTEX COLORING. Reduction from 3-SAT to VERTEX COLORING.
• Satisfiabile, unsatisfiabile, and tautological Boolean expressions; coNP class, exixtential and universal non-deterministic machines. Relationships between known complexity classes.
• 2023-11-27
• The exponential-time class EXP
• EXP-complete languages: RESTRICTED HALTING.
• 2023-11-28
• Space complexity classes: L, NL.
• Examples of logarithmic-space languages. The ST-CONNECTIVITY (STCON) language and its space complexity.
• 2023-12-04
• Savitch's theorem: NSPACE(f(n))=DSPACE(f(n)2), hence PSPACE=NPSPACE.