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

Basic information

Important news

[2024-02-19]
The text and solution outline of the 2024-02-19 exam is available in the Exams section.

[2024-01-17]
The text and solution outline of the 2024-01-08 exam is available in the Exams section.

Schedule

Last edition: Fall semester 2023, four hours per week.

Instructor

Mauro Brunato < mauro.brunato@unitn.it>

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

In order to receive urgent updates (e.g., about moved or cancelled lectures), please subscribe to the course's Moodle page.

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.
    • Randomized classes.

Textbooks

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 materials

This section contains course material and exercises.

Lecture notes

Example code

External links

(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 exams that are compatible with this year's program appear in the lecture notes. Here are links to the exam sheets as they were proposed during the academic years 2018-2019 and 2019-2020 (the three following years were taught by another instructor):

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.
  • 2023-12-11
    • Probabilistic time classes RP, coRP, ZPP.
    • Examples of languages in RP and coRP: balanced/constant functions, the Polynomial Identity Test.
  • 2023-12-12
    • Probabilistic time classes BPP and PP, their relationships with one another and with P, NP.
    • Quantum computing (quick mention): the BQP class.
    • More NP-complete problems: reduction from 3SAT to HAMILTONIAN PATH.
  • 2023-12-18
    • More NP-complete problems: Hamiltonian cycles in directed and undirected graphs.
    • NP-completeness of the Traveling Salesman Problem.
    • Discussion of exercises; complexity of INDSET for constant size k.
  • 2023-12-19
    • Discussion of exercises.