Maximale Anzahl positiver Literatur in 2sat

Question

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?

Answer 1

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.