Abstract: We characterized those coloring problems which are fully described by finitely many "obstructions" (i.e. finitary good characterizations). We present this and survey related research.
Abstract: Gegeben eine Boolesche Formel in konjunktiver Normalform mit n Variablen und m Klauseln, wobei jede Klausel genau drei Variablen enthalten soll, die aber nicht notwendig verschieden sein müssen, so fragt MAX-3-NAE-SAT nach einer Belegung der Variablen, so dass möglichst viele Klauseln erfüllt sind. Eine Klausel gilt als erfüllt, wenn jeweils mindestens eine Variable mit TRUE und eine mit FALSE belegt ist (NAE : not all equal).