Ist das Problem "Teilmenge Produkt" NP-vollständig?

Das Teilmengenproblem ist ein klassisches NP-vollständiges Problem:

Gibt es bei einer gegebenen Liste von Zahlen und einem Ziel eine Teilmenge von Zahlen von , die sich zu summiert ? $L$ $k$ $L$ $k$

Ein Student fragte mich, ob diese Variante des Problems mit der Bezeichnung "Teilmengenprodukt" NP-vollständig ist:

Gibt es bei einer gegebenen Liste von Zahlen und einem Ziel eine Teilmenge von Zahlen aus deren Produkt ? $L$ $k$ $L$ $k$

Ich habe ein bisschen gesucht und konnte keine Ressourcen finden, die über dieses Problem sprachen, obwohl ich sie vielleicht verpasst habe.

Ist das Subset-Produktproblem NP-complete?

complexity-theory np-complete reductions templatetypedef
quelle

Interessante Antworten, aber ich frage mich: Können wir nicht auf die Teilmenge Summe reduzieren, indem wir nur k und alle Zahlen protokollieren? (Vielleicht sollte ich eine separate Frage stellen?)

j_random_hacker

@j_random_hacker, ja, wenn Sie nach der Suche auf dieser Website und online keine Antwort finden, schlage ich vor, dass Sie eine separate Frage stellen. Es ist eine nette Frage mit einer netten Antwort (Hinweis: Wenn Sie Protokolle erstellen, erhalten Sie etwas, das keine ganze Zahl ist; in der anderen Richtung sollten Sie darüber nachdenken, wie sich die Potenzierung auf die Größe der Zahlen auswirkt), aber es ist eine Art Tangente und wäre besser in seiner eigenen Frage.

@DW: Danke, wenn ich Zeit habe, mache ich was du vorschlägst!

j_random_hacker

Antworten:

In einem Kommentar wird eine Reduzierung von X3C auf SUBSET PRODUCT erwähnt, die Yao zugeschrieben wird. Angesichts des Ziels der Reduzierung war es nicht schwer zu erraten, wie wahrscheinlich die Reduzierung gewesen war.

Definitionen:

GENAUE ABDECKUNG BEI 3 SÄTZEN (X3C)

Gegeben eine endliche Menge mit ein Vielfaches von 3, und eine Sammlung von 3-Elementuntergruppen von , hat eine exakte Abdeckung enthalten für , wobei und jedes Element in in genau einmal vorkommt ? $X$ $|X|$ $C$ $X$ $C$ $C'$ $X$ $C' \subseteq C$ $X$ $C'$

TEILSATZPRODUKT

Gibt es bei einer gegebenen Liste von Zahlen und einem Ziel eine Teilmenge von Zahlen aus deren Produkt ? $L$ $k$ $L$ $k$

So reduzieren Sie eine X3C-Instanz auf eine SUBSET PRODUCT-Instanz:

Erstellen Sie eine bijektive Zuordnung zwischen den Mitgliedern von und dem ersten Primzahlen. Ersetzen Sie die Member von und den Subsets durch die zugeordneten Primzahlen. $X$ $|X|$ $X$ $C$
Multiplizieren Sie für jede Teilmenge in ihre Mitglieder. Die resultierende Produktliste ist für die SUBSET PRODUCT-Instanz. Da für die Abbildung in Schritt 1 Primzahlen verwendet werden, ist die Gleichwertigkeit der Produkte garantiert, wenn die Teilmengen nach dem Satz der eindeutigen Faktorisierung gleichwertig sind . $C$ $L$
Multiplizieren Sie die Mitglieder von zusammen; Das resultierende Produkt ist der Wert für die SUBSET PRODUCT-Instanz. $X$ $k$

Die Primfaktoren von sind genau die Elemente von . Die Primfaktoren der Zahlen in entsprechen genau den Mitgliedern der Teilmengen. Daher kann jede Lösung für die neue SUBSET PRODUCT-Instanz in eine X3C-Lösung umgewandelt werden, indem die Lösungsmitglieder von wieder den Teilmengen in . $k$ $X$ $L$ $C$ $L$ $C$

Jeder der drei Transformationsschritte umfasst Operationen, die für die Größe der Eingabe polynomisch sind oder die Größe eines Elements . Der erste Primzahlen können in der Zeit O ( ) unter Verwendung des Siebs von Eratosthenes erzeugt werden und werden durch den Primzahlsatz garantiert in den Raum eingepasst . $|X|$ $X$ $|X|$ $|X|$ $O(|X|^2 \ln |X|)$

Kyle Jones
quelle

+1, aber für die Reduktion denke ich, dass wir das erste | X | benötigen Primzahlen können in einer Anzahl von Bits dargestellt werden, die in | X | polynomisch sind - Habe ich recht, und wenn ja, haben wir diese Garantie?

j_random_hacker

Hervorragender Punkt. Ich habe einen Absatz hinzugefügt, um das anzusprechen.

Kyle Jones

Danke, dass der Satz es zementiert! Nicht um zu picken, aber laut der Seite, auf die Sie verlinkt haben, ist die k-te Primzahl ungefähr k log k, und da das Eratosthenes-Sieb anscheinend alle Primzahlen bis zu n in der Zeit O (n log log n) berechnet , wobei n = eingesetzt wird k log k scheint eine Zeit von O (k * log (k) * log (log (k log k))) anstelle von O (k) (Ihr O (| X |)) zu geben, um das erste k zu berechnen Grundierungen auf diese Weise.

j_random_hacker

Kyle Jones, ist es nicht kritisch, dass Schritt 3 eine Zahl

exponentieller Größe erzeugt? Verkürzt sich die Polynomzeit wirklich?

k

$k$

user1742364

@ user1742364 Nein, da für die Berechnung von

keine exponentielle Anzahl von Operationen oder das Speichern einer exponentiellen Anzahl von Bits erforderlich ist. Computing

benötigt

Multiplikationen und Multiplikationen sind im schlimmsten Fall eine

-Operation. Während

exponentiell größer als die größte Primzahl wird

, die Anzahl von Bits zu speichern benötigt

wird

k

$k$

k

$k$

| X |

$|X|$

O (n^{2})

$O(n^2)$

k

$k$

P

$P$

X

$X$

k

$k$

O (\log P)

$O(\log P)$

Kyle Jones

Nach [ 1 ]: Ja, das ist es

Ich zitiere auch den gleichen Verweis: Anmerkungen: Es gibt eine subtile technische Unterscheidung zwischen diesem und dem Problem 42: Der erstere Fall hat einen pseudoeffizienten Algorithmus, der erhalten wird, indem Zahlen unär dargestellt werden können; Solange nicht alle NP-vollständigen Probleme mit schnellen Algorithmen gelöst werden können, kann das Subset-Produktproblem auch mit dieser unvernünftigen Eingabedarstellung nicht mit "effizienten" Methoden gelöst werden.

Werfen Sie einen Blick auf [2] für eine Reduzierung. [2]: Fellows, Michael und Neal Koblitz. "Komplexität und Kryptographie mit festen Parametern." Angewandte Algebra, Algebraische Algorithmen und Fehlerkorrekturcodes (1993): 121-131.

AJed
quelle

Eine tatsächliche Verkleinerung oder Zitierung in einem Zeitschriftenartikel wäre, wenn möglich, nett.

Templatetypedef

@templatetypedef Bei Garey und Johnson beträgt die Reduzierung genau 3 Sätze. Aufgrund privater Kommunikation mit Yao.

AJed

Die Reduzierung des Kryptographiepapiers ist für ein anderes Problem, bei dem das Zielprodukt durch Kongruenz mit einer in der Instanz angegebenen Zielzahl Modulo Modulo ersetzt wird. (Wenn ich den Beweis richtig verstehe, erhalten sie ohnehin nur eine schwache Härte, da der Modul in seiner Größe exponentiell ist.)

Jeffrey Bosboom