The NP-completeness of the problem can be shown, for example, by a reduction from maximum 2-satisfiability (a restriction of the maximum satisfiability problem).
NP kompletnost se može pokazati, na primer, transformacijom iz maksimum 2-zadovoljivosti ( koji je restrikcija problema maksimalne zadovoljivosti).