Maximale Anzahl positiver Literatur in 2sat
-
29-09-2020 - |
Frage
max 2sat ist np komplett.
Anstatt die maximale Anzahl von Klauseln zu befriedigen, habe ich eine voll befriedigende 2sat-Formel und möchte die maximale Anzahl positiver Literatur in der Zuordnung (so dass alle Klauseln natürlich zufrieden sind).
Was ist die Schwierigkeit dieses Problems?
Lösung
Dieses Problem ist np-hart (und zusätzlich schwer zu annähernd und w [1] -Hard), da maximal unabhängige Set darauf reduziert werden kann.Reduktion: Jede Variable repräsentiert einen Scheitelpunkt und jede Klausel stellt eine Kante dar.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange