Logical Aspects of Computation, Spring 2026

ETH Zürich: Course Catalog

Course Description

Why are some computational problems easy and others seemingly impossible? This question sits at the heart of theoretical computer science, and most of the seminar’s participants have already been exposed to basic results about decidability and NP-completeness before (252-0057-00L). Building on this basis, this seminar approaches computation from the logical perspective, an angle which is rarely integrated into the undergraduate curriculum.

The seminar unfolds over two units. The first unit focuses on the nature of NP. We begin with a review of Cook and Levin’s proof that Boolean satisfiability is NP-complete (Cook 1971; Levin 1973). We then turn to a more obscure result, but, in the opinion of the lecturer, a deeper result: Fagin’s characterisation of NP as the class of problems expressible in existential second-order logic (Fagin 1974). A central ambition of this unit is to construct, collaboratively, a meta-theorem that reveals these two results as expressions of the same underlying idea, and to appreciate why Fagin’s theorem, operating at the level of logical expressibility rather than individual reductions, achieves something more uniform. (We will briefly explain the notion of uniformity in the theory of computation.) The second unit turns to alternation (Chandra, Kozen and Stockmeyer 1981), a simple generalisation of nondeterminism that generates the entire polynomial hierarchy (Stockmeyer 1976) and connects the structure of complexity classes to the structure of logical quantifiers. Each unit pairs close engagement with the theoretical results with hands-on implementation in Python, because it is in the code that the mathematics becomes tangible.

Course Structure and Schedule

This seminar will be taught in the spirit of Freire’s Pedagogia do Oprimido [Pedagogy of the Oppressed] (Freire 1968). For Freire, the great failure of traditional education is what he calls the banking model. In the metaphor, the teacher is a depositor, the student is a passive receptacle, and education is an inert transfer of facts. Militating against this, Freire insists that genuine understanding is always constructed in dialogue—between people grappling with ideas together, and, in this seminar, between a student and their Python interpreter as they work to make their implementations pass the unit tests.

Attendance is not taken and is not mandatory. Moreover, everyone receives a 6. These are not loopholes. They are a deliberate refusal to let fear or coercion do the work that curiosity should. Come to class because you are curious. That is enough.

Time: Friday 12:15-14h

Location: CAB G 52 (first session: CHN D 29)

Bibliography

• Stephen A. Cook (1971). The complexity of theorem-proving procedures.

• Leonid A. Levin (1973). Универсальные задачи перебора (transl. Universal sequential search problems).

• Ronald Fagin (1974). Generalized first-order spectra and polynomial-time recognizable sets.

• Larry J. Stockmeyer (1976). The polynomial-time hierarchy.

• Ashok K. Chandra, Dexter C. Kozen, and Larry J. Stockmeyer (1981). Alternation.

• Paulo Freire (1968). Pedagogia do Oprimido (Pedagogy of the Oppressed).