Constraint Satisfaction Probleme
Constraint Satisfaction Probleme (CSP) sind eine große Teilklasse von NP, die unter anderem 3SAT, 2SAT, 2-Färbbarkeit und 3-Färbbarkeit enthält (sogar k-SAT und k-Färbbarkeit für jedes k). Wir sehen uns an, wie CSPs definiert sind, wie sie als Homomorphismenproblem aufgefasst werden können, und erwähnen einige Dichotomie-Resultate.