Teilmenge Summe vs. Teilmenge Produkt (starke vs. schwache NP Härte)

Ich hatte gehofft, jemand könnte mir erklären, warum genau das Subset-Produktproblem stark NP-hart ist, während das Subset-Summenproblem schwach NP-hart ist.

Subset Summe: Bei und , Gibt es eine Teilmenge so dass . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\sum_{i\in X'}x_i = T$

Subset Produkt: Da und , Gibt es eine Teilmenge so dass . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\prod_{i\in X'}x_i = T$

Ich dachte immer, die beiden Probleme wären gleichwertig - eine Instanz von SS könnte durch Potenzierung in eine Instanz von SP und eine Instanz von SP durch Logarithmen in SS umgewandelt werden. Dies führte mich zu dem Schluss, dass beide zu derselben Klasse von NP-Hard gehörten - dh, sie waren beide schwach NP-Hard.

Ferner scheint es, dass dieselbe Wiederholung verwendet werden könnte, um beide Probleme unter Verwendung dynamischer Programmierung mit einer sehr geringen Änderung zu lösen (wobei die Subtraktion in SS durch die Division in SP ersetzt wird).

Das war, bis ich Kapitel 8 von "Theory of Computation" von Bernard Moret gelesen habe (für diejenigen ohne das Buch gibt es einen Beweis für die Härte des Teilmengenprodukts über X3C - ein stark NP-hartes Problem).

Ich verstehe die Reduktion, kann aber nicht herausfinden, was mit meiner früheren Schlussfolgerung (Gleichwertigkeit der beiden Probleme) falsch war.

UPDATE : Es stellt sich heraus, dass das Teilmengenprodukt nur schwach NP-vollständig ist (das Zielprodukt ist in exponentiell ). Gary und Johnson haben dies 1981 in ihrer NP-Vollständigkeitskolumne veröffentlicht , aber ich denke, es war weniger sichtbar als ihre frühere Behauptung in ihrem Buch. $\Omega (n)$

cc.complexity-theory np-hardness reductions subset-sum RDN
quelle

Wahrscheinlich wäre es gut sich vorzustellen, wie Sie Ihren dynamischen Programmieralgorithmus implementieren würden. Dann würden Sie finden, was falsch war.

Yoshio Okamoto

@ MohammadAl-Turkistany: Es ist im letzten Abschnitt dieser Kolumne

RDN

Antworten:

In Bezug auf das Problem der Äquivalenz von Teilmenge Summe und Teilmenge Produkt gibt es eine technische Besonderheit in Bezug auf Teilmenge Produkt. Das Produkt von x = T ist tatsächlich ein Pseudopolynom, wenn T nicht exponentiell ist! Die Beweise, dass Subset Product NP Hard ist, sind also (aus technischen Gründen !!!) nicht ganz korrekt!

Wenn man jedoch verspricht, dass T groß ist, ergibt die Reduktion über Logarithmen auf die Teilmengen-Summe eine NICHT-STANDARD-Teilmengen-SUMME, die über dem Real liegt! Dies bedeutet, dass der Pseudopolynom-Algorithmus für die Teilmengen-Summe nicht gilt! Obwohl die Logarithmen klein sind, verfälschen die Dezimalstellen die dynamische Programmierung des Pseudopolynoms!

ich hoffe das hilft

Zelah

Zelah 02
quelle

Es stellte sich heraus, dass Sie die ganze Zeit über Recht hatten, dass die Reduktionen falsch waren (dh, Sie behaupten, dass sie eine starke NP-Vollständigkeit aufweisen, wenn sie dies nicht tun). Vielen Dank!

RDN

Erstens funktioniert die Verwendung der Exponentiation für den Übergang von SS zu SP (mit Basis 2 anstelle von Basis ), erhöht jedoch die Größe der beteiligten Zahlen. Eine schwache NP-Härte bedeutet, dass das Problem nicht länger schwer ist, wenn die Zahlen klein sind (genauer gesagt, unär). Daher werden durch die Verwendung der Exponentiation SP-Instanzen mit exponentieller Größe erstellt, auch für einfache SS-Instanzen, bei denen die Zahlen unär geschrieben sind. $e$

Zweitens funktioniert die Verwendung von Logarithmen für den Übergang von SP zu SS nicht, da Logarithmen normalerweise nicht ganzzahlige Werte generieren. SS und SP werden mit ganzzahligen Zahlen definiert, und Logarithmen führen oft zu transzendentalen Werten, die schwer darzustellen oder zu berechnen sind.

<edit>

Sei eine ganze Zahl, , dann ist nur dann rational, wenn eine Potenz von 2 ist, und ansonsten transzendental. Erstens, wenn $A$ $A > 0$ $\log_2 A$ $A$ für ganze Zahlen ungleich Nullund, dann ist $\log_2 A = \frac{p}{q}$ $p$ $q$ ,. Wir haben alsodurch Primzerlegung. Außerdem ist, alsokönnen wir beigegebenemundwählen,zu beweisen, dassrational ist. $A = 2^{\frac{p}{q}}$ $A^q = 2^p$ $A = 2^r$ $A^{rq} = 2^p$ $A$ $q=1$ $p=r$ $\log_2 A$

Wir müssen nur zeigen, dass niemals transzendental ist. Dies folgt aus dem Gelfond-Schneider-Theorem , denn eine äquivalente Formulierung (wie auf der Wiki-Seite zu finden) lautet: "Wenn und algebraische Zahlen ungleich Null sind und wir einen von Null verschiedenen Logarithmus von annehmen , dann ist entweder rational oder transzendental. " Es ist auch einfach , indem man die Umkehrung des Satzes und Einstellung zu überprüfen und damit $\log_2 A$ $\alpha$ $\gamma$ $\alpha$ $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ $\alpha^\beta = \gamma$ . $\beta = \log_\alpha \gamma$

</edit>

Als letztes überlegen Sie, was passiert, wenn wir den dynamischen Programmieralgorithmus von SS auf SP ausprobieren. Da wir Produkte anstelle von Summen verwenden, explodieren die Zahlen enorm, und die willkürliche Genauigkeit, die erforderlich ist, wird plötzlich zu einem Faktor in der Laufzeit. Aus diesem Grund kann der Algorithmus SP-Instanzen nicht schnell lösen, selbst wenn die Zahlen unär sind.

Alex ten Brink
quelle

Dies führt zu einem etwas interessanten Sonderfall. Für welche Klassen von Zahlen kann das Protokoll als Rational ausgedrückt werden und erfordert keine unendliche Präzision? In diesem Fall wären die Probleme in der Tat nahezu gleichwertig und zueinander reduzierbar. es scheint auch zu einem "natürlichen" Näherungsalgorithmus zu führen.

vzn

Danke für die tolle Antwort! Ich habe nur ein Problem - ich verstehe, warum das Nehmen von Protokollen illegal ist (außer vielleicht in dem Fall, in dem die Protokolle poly lang sind - wie vzn betont), aber ich bin mir immer noch nicht sicher, ob es legal ist, von SS zu SP zu wechseln durch Potenzierung. WRT von SS SP gehen , wie Sie (über Potenzierung) erwähnt, nicht laufen wir in das folgende Problem: Die Anzahl der Bits in der Eingabeinstanz von

ist

und die Anzahl der Bits in der Instanz von

ist

. Dies ist eine exponentielle Explosion. Also ist es immer noch legal? Wenn ja, warum?

I_{S S}

$I_{SS}$

O (n \log x)

$O(n\log x)$

I_{S P}

$I_{SP}$

O (n x)

$O(nx)$

RDN

@vzn, RDN: Ich habe eine Charakterisierung bearbeitet, wenn der Logarithmus transzendental ist. Über die Vergrößerung der Reduktion hängt es von Ihrer Definition von 'legal' ab: Die Reduktion ist korrekt , aber ihre Effizienz ist nicht polynomial und sagt daher nichts über die NP-Härte aus. Es handelt sich also nicht um eine korrekte Mehrfachzeitverkürzung , sondern um eine korrekte Verkürzung (ohne Qualifikatoren).

Alex ten Brink

Es gibt auch einen Sonderfall, in dem alle Zahlen in der Form

vorliegen , wobei jedes

für jedes

rational ist , nicht nur für

. der Näherungsalgorithmus, an den ich dachte, könnte ein

so dass die Umwandlung von Werten in diese "Basis" den Originalen "nahe" kommt.

c^{n_{i}}

$c^{n_i}$

n_{i}

$n_i$

c

$c$

c = 2

$c=2$

c

$c$

vzn

Die wörtliche Erklärung ist, dass das Subset-Produktproblem NP-vollständig ist, indem es von einem stark NP-vollständigen Problem, wie der exakten Abdeckung durch 3-Sätze, reduziert wird. Bei einer solchen "starken" Reduzierung sind die Eingabe-Ganzzahlen durch eine Polynomfunktion in der Anzahl der Ganzzahlen in der resultierenden Instanz des Subset-Produktproblems begrenzt.

Eine solche „starke“ Reduktion ist von jeder stark NP-vollständiges Problem zu Subset - Sum Problem , es sei denn unmöglich . Wir haben einen dynamischen Programmieralgorithmus für die Polynomzeit, um das Subset-Summen-Problem zu lösen, wenn Eingabe-Ganzzahlen durch ein Polynom begrenzt sind. $P=NP$

Mohammad Al-Turkistany
quelle

Ja ich verstehe das. Meine Frage war, warum die Schlussfolgerung, die ich zuvor gezogen hatte, falsch war (dh die Gleichwertigkeit von SS und SP).

RDN

@rdn Es gibt in diesem Sinne keine Äquivalente, es sei denn, P = NP.

Mohammad Al-Turkistany

Ja, das verstehe ich. Aber ich möchte wissen, was an meinen Nachlässen in beide Richtungen falsch war.

RDN

Können Sie Ihre Ermäßigungen skizzieren?

Mohammad Al-Turkistany

Lassen Sie

. Verwandlung

I (S S) = ⟨ X, S ⟩

$I(SS)=\langle X, S \rangle$

I (S P) = ⟨ Y, P ⟩

$I(SP)=\langle Y, P \rangle$

I (S S)

$I(SS)$

I (S P)

$I(SP)$

P = e^{S}

$P = e^S$

Y_{i} = e^{X_{i}}

$Y_i = e^{X_i}$

S

$S$

P = e^{S}

$P = e^S$

I (S P)

$I(SP)$

I (S S)

$I(SS)$

S = l o g (P)

$S = log(P)$

X_{i} = \log (Y_{i})

$X_i = \log(Y_i)$

P

$P$

S = \log (P)

$S = \log(P)$