Ist das folgende Problem in NP-Complete oder P?
Eingang: Eine Menge S positiver Ganzzahlen {a1, a2, ..., an) und eine positive ganze Zahl M.
Frage: Gibt es eine Teilmenge S "von S, so dass alle Elemente in S" entweder M-1, M oder M + 1 ergeben.
Ich vermute, dass es sich um NP-Complete handelt und sich auf die Teilmenge bezieht. Es fällt mir jedoch schwer, die Teilmengen auf dieses Problem zu reduzieren.
Antworten:
0 für die Antwort № 1Dies ist NP-vollständig. Gegeben eine Instanz der Teilmengen-Summe
Finden Sie eine Teilmenge von {x1, ... xn} mit der Summe X.
Betrachten Sie die folgende Instanz Ihres Problems
Finden Sie eine Teilmenge von {4 * x1, 4 * x2, ..., 4 * xn} mit der Summe 4 * X, 4 * X-1 oder 4 * X + 1
Wenn man die Teilbarkeit von 4 betrachtet, ist das klarJede Teilmenge, die sich zu 4 * X, 4 * X-1 oder 4 * X + 1 summiert, muss tatsächlich 4X summieren. Dies gibt dann aber trivial eine Lösung für das ursprüngliche Subset-Sum-Problem, indem es durch 4 geteilt wird.