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

Basic information

Important news

[2025-01-17] The text of the written exam from the first session is available in the materials section together with a proposed solution trace.

Schedule

Four hours per week. The 2024-25 edition is over.

Instructor

Mauro Brunato < mauro.brunato@unitn.it>

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

Course syllabus

Objectives

The course aims at providing the theoretical bases for understanding two fundamental properties of computational problems.

  1. Given a problem, at first we will 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?
    • Are there any intrinsically unsolvable problems?
  2. 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 way to classify problems with respect to their hardness?
    • Does this classification tell us anything about the limits of our capability to solve problems?

Entrance requirements

Students should have a basic understanding of the following topics:

  • Mathematical logic: logical connectives, quantifiers, basic propositional calculus; being able to follow the proof of simple theorems.
  • Mathematics: polynomials, logarithms, exponentials; positional representation of integers in different bases.
  • Programming, algorithms and data structures: knowledge of a specific programming language is not required, but being able to describe algorithms and data structures is essential.

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. Cook-Levin Theorem. Study of NP-complete problems.
    • Space complexity classes: LOGSPACE, NLOGSPACE, PSPACE, NPSPACE. Savitch's theorem.

Expected learning outcomes

At the end of the course, 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-Levin 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.

Teaching and learning methods and activities

The course will mainly consist of lectures and discussions with students.

As soon as specific milestones are reached, exercises and papers will be proposed for self-assessment and further discussion.

Since the beginning of the course, the previous year's material will be made available on this website (in the materials section below):

  • Lecture notes
  • Example code
  • Solved exercises
  • Exam sheets from previous years
  • Relevant papers and webpages.
The material will be updated during the semester.

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]

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

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Pearson new International Edition, 2013. ISBN: 9781292039053

Test and assessment criteria

The exam is written, pen and paper, in English, and is composed by three open-question exercises requiring to expose theoretical topics and analyze problems and algorithms. One of the exercises is about computability, the other two are mainly about the computational complexity topic. The three exercises have an equal weight in determining the final mark.

Answers are evaluated on the basis of the following criteria:

  • Correctness: the answers must follow a logical path, consistent with the course topics and with the question; however, given that the discipline is still young, personal opinions are welcome, as long as they are motivated.
  • Relevance: going off-topic in the hope to collect some points doesn't usually work.
  • Motivation: the answers provided by the student must enable the examiner to follow the logical path leading to their formulation; answers without explanations are not taken into account.
  • Clarity: short and precise answers, with the correct use of technical terminology and without ambiguities are preferred.
Students have free access to the exam sheets of the previous sessions on the course website.

Quick stats

In the winter and summer exam sessions of 2024, 61 registrants out of 66 have passed the exam (38 out of 42 in the first exam in January).

Course materials

This section contains course material and exercises.

Lecture notes

Lecture videos

Example code

External links

(See the lecture notes for details)

Past exams

Current year

Previous years

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, 2019-2020 and 2023-2024 (the three missing years were taught by another instructor):

Exams

  • See the course syllabus above for a comprehensive description of the exam and of the assessment criteria.
  • All tests from the previous years are available in the materials section above.
  • The next exam session will take place on Winter 2025 on the following dates:
    Date/timeRoom
    First callThursday, January 9th, 2025 09:00a,—12:00pmB107 (conference room in Povo2)
    Second callMonday, February 17th, 2025 09:00a,—12:00pmB107 (conference room in Povo2)

Detailed program and lecture videos

This Section will be updated during the year.

2024-09-09

  • Basic definitions: alphabet, string, language. Enumerating strings.
  • Enumeration of countable sets, diagonal proofs of uncountability.

2024-09-10

  • Examples of potentially infinite computations based on some unsolved mathematical conjectures (Collatz).
  • Intuitive definitions of recursive and recursively enumerable sets. Diagonal procedure to enumerate R.E. sets.
  • Turing machines: intuition, introduction.

2024-09-16

  • Turing machines: examples. Using the states to “store” finite amounts of information (e.g., bits).
  • Multiple-tape Turing Machines.
Note: the recording was interrupted at 28:15 and resumed a few minutes later; the missing part is the transcription of the state diagram of the Turing machine on the blackboard into the simulator; the completed transcription can be seen in the upper left picture after the cut.

2024-09-17

  • Computational power of Turing machines: multiple tapes, alphabet size. Reduction to 1-tape, 2-symbol machines with quadratic time loss.

2024-09-23

  • Universal Turing machines: string encodings of TMs, simulation of TMs.
  • Proof of uncomputability by diagonalization.

2024-09-24

  • Uncomputability of the halting problem.
  • The Church-Turing thesis.
  • Recursive and recursively enumerable languages: Recursive enumerability of HALT.
Note: an intermediate 20' segment was lost because the computer entered sleep mode. Likewise, the final 30' are lost. The following is an approximate timeline of the lecture with pointers to the lecture notes for the missing parts.
  • 00'00"—19'50" from the video, first recorded segment: summary of the previous lecture; why is UC uncomputable?
  • 20' missing footage: in order to compute UC, we need to know if the computation of Ms(s) halts, so we would like to have a TM that tells us if a generic computation M(s) halts. Let us call this machine H (text before Theorem 4 in the notes, page 14).
  • 20'00"—40'00" from the video, second recorded segment: proof by contradiction that machine H, computing function HALT, cannot exist (Theorem 4 in the notes, pages 14–15).
  • 30' missing footage: The Church-Turing Thesis (section 1.2.4 in the notes, page 13); although HALT is not recursive, it is recursively enumerable (Section 1.2.6 of the notes, pages 15–16).

2024-09-30

  • Recursive and recursively enumerable languages, clarifications about the equivalence of different definitions.
  • Turing reductions (introduction).

2024-10-01

  • Co-recursively enumerable languages, relationship between R, RE and coRE.
  • Variations of the halting problem: machines on empty inputs.
  • The Busy Beaver game.

2024-10-07

  • The Busy Beaver game (continued).
  • Uncomputable busy beaver numbers: links to propositional logic via the unprovable consistency of the Zermelo-Fraenkel axiomatic set theory.

2024-10-08

  • Properties of TMs as decision functions or sets.
  • Trivial properties; semantic properties.
  • Statement and proof of Rice's Theorem

2024-10-14

  • Discussion of Exercise 36 from the lecture notes (recursive and RE sets, recursivity of TM properties).
Note: the initial 20' were not recorded, however the initial part of the exercise is quite straightforward.

2024-10-15

  • Turing completeness.
  • An example of Turing-complete problem: Post's Correspondence Problem.

2024-10-21

  • Random and compressible strings.
  • Kolmogorov complexity: definition, properties, non-computability.

2024-10-22

  • Turing reductions.
  • Exercises about recursive and RE sets.

2024-10-28

  • Exercises on Turing machines and about the recursivity of TM properties.

2024-10-29

  • Exercises on Turing machines and about the recursivity of TM properties (continued).

2024-11-04

  • Computational complexity: introductory remarks; deterministic time classes DTIME(f); the polynomial-time class P.
  • Examples of languages in P: CONNECTIVITY, COMPLETE, k-CLIQUE (for a fixed value of k).
  • Examples of languages with no known polynomial-time decision algorithms: CLIQUE (with arbitrary size parameter).

2024-11-05

  • More examples of languages in P: PRIME (prime numbers).
  • Examples of languages with no known polynomial-time decision algorithms: ILP (integer linear programming), SATISFIABILITY (of Boolean CNF formulas).

2024-11-11

  • Non-deterministic Turing machines; non deterministic time classes, the class NP and its characterization.
  • Polynomial-time reductions (introduction); reduction of INDEPENDENT SET (INDSET) to CLIQUE.

2024-11-12

  • Definition of polynomial-time reductions.
  • Reduction of SAT to ILP and 3SAT, reduction of 3SAT to INDSET.

2024-11-18

  • Definition of TM transition functions as truth tables, Boolean formulas, Boolean circuits.
  • Properties of Boolean operators; characterization of Boolean gates (AND, OR, NOT) and Boolean circuits by means of a 3-CNF formula.

2024-11-19

  • Polynomial reduction of an NDTM's computation to a Boolean circuit with choice bits to a 3-CNF Boolean formula.
  • Cook-Levin's Theorem: 3-SAT is NP-complete.

2024-11-25

  • More NP-complete languages: 3-VERTEX COLORING, SUBSET SUM.

2024-11-26

  • Disjunctive Normal Form and the TAUTOLOGY language.
  • The coNP time class, existential-mode and universal-mode NDTMs.
  • Relationship between P, NP, and coNP; the FACTORING decision language; probable non-completeness of GRAPH ISOMORPHISM.

2024-12-02

  • The exponential-time class EXP and its relationship with NP and coNP.
  • An EXP-complete language: RESTRICTED HALT.
  • Space complexity classes: the deterministic polynomial space complexity class PSPACE and its relationships with the known time complexity classes NP, coNP and EXP.

2024-12-03

  • The logarithmic-time classes L and NL.
  • A language in NL: ST-CONNECTIVITY (STCON).
  • Relationships among L, NL and the other complexity classes.

2024-12-09

  • Logarithmic space classes: ST-CONNECTIVITY is NL-complete, ST-CONNECTIVITY is DSPACE((log|x|)2).
  • Savitch's Theorem: NSPACE(f(n))=DSPACE(f(n)2).
  • Consequences of Savitch's Theorem: NPSPACE=PSPACE.

2024-12-10

  • Proofs of NP-completeness: KNAPSACK, VERTEX COVER, HAMILTONIAN PATH/CYCLE, TSP (the Traveling Salesman Problem).

2024-12-16

  • Exercises: Computability and Rice's Theorem, Computability of Bounded PCP, (co)NP-completeness of SHORT SIMPLE PATH, LONGEST PATH.

2024-12-17

  • Clarifications on Bounded PCP.
  • Exercises: BOX DEPTH, reduction to CLIQUE, polynomial decision algorithm; CIRCUIT SAT and reductions to 3SAT; BOTTLENECK TSP, reduction from HAMILTONIAN CYCLE.