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

## Basic information

#### Important news

[2020-01-19]
The text and the solution outline of the 2020-01-15 exam are available in the Exams section.

[2020-01-02]
Complete lecture notes and exercises in the Materials section.

#### Schedule

Fall semester, four hours a week.

Lessons are over.

#### Instructor

Mauro Brunato < mauro.brunato@unitn.it>

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

Note for returning students — To avoid spamming, last year's subscriptions have been removed; if interested, please re-subscribe.

## 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.
• 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).

#### 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

### Lecture notes

• 2020-01-02 version: notes are now complete; further versions might be published in case of important errata.

### Example code

(See the lecture notes for details)

## Exams

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.

The next exam session will take place during the Winter break (January/February 2020):

First call Second call Wednesday, January 15 2020, 0900-1200 Room A105 Wednesday, February 12 2020, 0900-1200 Room A104

### Past exams

• Winter session: first call exam text and solution outline.
• Exercises from previous years' exams that are compatible with this year's program appear in the lecture notes.

## Course program

• 2019-09-18
• Basic definitions: alphabet, string, language. Enumerating strings.
• Existence of uncountable sets (e.g., real numbers): there are not enough strings to describe all real numbers.
• 2019-09-19
• 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.
• 2019-09-25
• Common methods to recognise languages: automata, grammars, regular expressions.
• Turing machines; representation of their transition function as a table or as an automaton. Examples.
• 2019-09-26
• Computational power of Turing machines: multiple tapes, alphabet size, extension of the tape.
• Emulation of a Von Neumann machine with a Turing machine (hints).
• 2019-10-02
• Universal Turing machines: string encodings of TMs, simulation of TMs.
• Uncomputable functions: their existence by cardinality argument, proof of uncomputability. Uncomputability of the halting problem.
• 2019-10-03
• Special restricions of the halting problem: machines starting from an empty tape.
• Recursive and recursively enumerable languages; co-R.E. languages.
• 2019-10-09
• Busy beaver functions and their uncomputability.
• Reductions, Turing reductions. Proofs by reduction: general framework.
• 2019-10-10
• Discussion: computability of the halting problem for restricted classes of TMs.
• 2019-10-16
• Consequences of the uncomputability of the halting problem; oracles and computability.
• Semantic properties of TMs and Rice's theorem.
• 2019-10-17
• Example of uncomputable problem outside of CS: Post's Correspondence Problem.
• 2019-10-24
• Examples of TM properties and applications of Rice's Theorem.
• Example of uncomputable problems: Kolmogorov complexity.
• 2019-10-30
• Computational complexity: basic definitions.
• Time classes: DTIME(f), P, EXP. Examples.
• 2019-10-31
• CNF Boolean expressions, SATISFIABILITY (SAT), CLIQUE, the Traveling Salesman Problem (TSP).
• 2019-11-06
• Characterization of class NP.
• Examples of NP problems: SATISFIABILITY, CLIQUE, TSP.
• 2019-11-07
• Polynomial reductions, examples for known NP problems.
• Definitions of NP-hard and NP-complete problems.
• Boolean circuits and CNF representations of a circuit.
• 2019-11-13
• Polynomial reduction of a (ND)TM's computation to a Boolean circuit.
• Cook's theorem: SAT is NP-complete.
• 2019-11-20
• Other NP languages: VERTEX COVER, INTEGER LINEAR PROGRAMMING (ILP), k-VERTEX COLORING.
• Reductions: INDSET to VERTEX COVER and to ILP, 3-SAT to 3-VERTEX COLORING.
• 2019-11-21
• Satisfiabile, unsatisfiabile, and tautological Boolean expressions.
• Exponential complexity classes: EXP and NEXP.
• 2019-11-27
• Deterministic and non-deterministic space complexity classes: L, NL, PSPACE, NPSPACE.
• The ST-CONNECTIVITY language.
• 2019-11-28
• Savitch's theorem: NSPACE(f(n))=DSPACE(f(n)2), hence PSPACE=NPSPACE.
• Probabilistic classes RP, coRP, ZPP.
• 2019-12-04
• Examples of languages in RP and coRP.
• Probabilistic classes BPP and PP.
• 2019-12-05
• More NP-complete problems: SET COVER, SUBSET SUM, KNAPSACK.
• 2019-12-11
• Application of NP-hardness results: the Merkle-Hellman Knapsack cryptosystem.
• More NP-complete problems: Hamiltonian paths and cycles in directed and undirected graphs.
• NP-completeness of the Traveling Salesman Problem.
• 2019-12-12
• Further directions of computational complexity theory: average-case complexity, possible consequences of P=NP, existence of one-way and trapdoor functions.
• 2019-12-18
• Discussion of exercises; complexity of CLIQUE for constant clique size k; consequences of allowing exponential reductions.