SAT-Kodierung: Anzahl-Constraints

count≥k(p1,…, pn) = wenigstens k der n Variablen sind wahr.

(Übung: definiere count=k, count≤k)

Anwendung: größte unabh. Menge von Springern?



2014-07-06