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

## Basic information

#### Important news

[2020-09-02]
The text and solution outline of the 2020-09-02 exam is available in the Exams 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

Temporary changes due to Covid-19 restrictions — The exam will consist in a 45-minute online written test during, followed by an oral interview during the same day. Precise connection and scheduling information will be sent to registered students the day before the exam.

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 Summer session is over; in 2020/2021 the course will be offered by another teacher (see Esse3 for details). For students of the past years, a final Winter session will be arranged upon request.

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