Interesuje mnie odmiana SAT, w której wzór CNF jest monotoniczny (żadnych zmiennych nie neguje się). Taka formuła jest oczywiście zadowalająca.
Ale powiedzmy, że liczba prawdziwych zmiennych jest miarą tego, jak dobre jest nasze rozwiązanie. Mamy więc następujący problem:
MINIMALNY PRAWDZIWY MONOTON 3SAT
INSTANCJA: Zestaw U zmiennych, zbiór C rozłącznych klauzul 3 literałów, gdzie literał jest zmienną (nie negowaną).
ROZWIĄZANIE: Przypisanie prawdy dla U, które spełnia C.
POMIAR: Liczba prawdziwych zmiennych.
Czy ktoś mógłby mi przekazać kilka pomocnych uwag na temat tego problemu?
źródło
źródło