Topic outline

  • CS-E4700 Logic and Hard Computational Problems

    This course is implemented in the A+ platform---please register to the course in Sisu.

    Basic information

    First lecture: Tuesday 5 September, 12--14, Hall AS3 (Maarintie 8).

    Overview. This is an intermediate-to-advanced-level optional course that introduces you to logical formalization of mathematical reasoning and to mathematics of computational intractability, with a four-fold motivation:

    1. Mathematical logic and logical reasoning are fundamental conceptual tools in the pursuit of mathematics and higher notions of artificial intelligence involving concepts such as explainability and trustworthiness. Mathematical logic in particular studies the concepts of mathematical proof and provability, as well as the fundamental limitations of such notions in terms of their expressive reach and computability.
    2. Logic is a versatile tool for modeling and inference in applications. We will work with propositional logic and predicate logic to model settings ranging from recreational puzzles and games to modeling computation and other mathematical pursuits.
    3. Logic is inherently connected with computation and computational hardness. For example, Boolean logic and Boolean circuits are the foundation of modern computing and a rich source of open problems concerning resource-efficient computation and the design of algorithms. Predicate logic is expressive enough to model resource-unbounded computation and is thus not algorithmically decidable, yet predicate logic admits a sound and complete proof system.
    4. Computational problems can be studied as formal mathematical objects and mathematically analysed for their computational hardness by (i) showing that one problem is at least as hard as another by means of an efficient algorithmic reduction; and (ii) classifying problems into formal complexity classes based on criteria such as resource consumption of algorithms or reducibility. This course gives you a rigorous introduction and working knowledge of the classes P and NP, as well as the class of NP-complete problems. The question whether P equals NP is among the most fundamental open problems in all of computing and mathematics.


    Prerequisites: BSc-level basic studies in mathematics and programming. Courses such as MS-A0402 Foundations of Discrete Mathematics and CS-C2160 Theory of Computation are assets.

    Teacher: Prof. Petteri Kaski.

    Grading: Total points awarded from weekly problem sets determine the course grade. No exam.

    Learning outcomes

    This course introduces you to logical formalization of mathematical reasoning and to mathematics of computational intractability. You learn to work with and reason using propositional logic and first-order logic. You learn how to prove that a computational problem is at least as hard as another computational problem by presenting an efficient reduction from the latter to the former. You know the problem classes P and NP, as well as the hardest problems in the class NP, namely the NP-complete problems. You learn how to prove that a computational problem is NP-complete.

    Lecture schedule (tentative)

    1. Propositional Logic (Tuesday 5 September).

    2. Modeling and Provability (Tuesday 12 September).

    3. Resolution and Relational Structures (Tuesday 19 September).

    4. Predicate Logic (Tuesday 26 September).

    5. Completeness, Undecidability, Incompleteness (Tuesday 3 October).

    6. Boolean Functions and Boolean Circuits (Tuesday 10 October).

    [Tuesday 17 October: Exam week --- no lecture.]

    [Tuesday 24 October: Break --- no lecture.]

    7. Problems and Reductions (Tuesday 31 October).

    8. The Classes P and NP (Tuesday 7 November).

    9. NP-Completeness and Beyond (Tuesday 14 November).