Résumé: An emerging area of research studies the complexity of constraint satisfaction problems under restricted constraint languages. This article gives a self-contained, contemporary presentation of Schaefer’s theorem on Boolean constraint satisfaction, the inaugural result of this area, as well as analogs of this theorem for quantified formulas. Our exposition makes use of and may serve as an introduction to logical and algebraic tools that have recently come into focus.

Langue: Anglais