Nachweis NP Schwere
-
Hallo,
um nachzuweisen, dass ein Problem NP schwer ist, reduziert man ja normalerweise ein NP vollständiges Problem auf dieses Problem.
Ich habe das nun andersherum gemacht: Ein spezieller Fall meines Problems, lässt sich auf ein NP vollständiges Problem reduzieren.
Ist das auch ein gültiger Nachweis von NP Schwere?
thx im Vorraus.
-
Nein, das geht so nicht.
Du kannst die Addition von n Zahlen auf Knapsack von n Zahlen mit je Gewicht 1 und Gesamtgewicht n reduzieren, aber trotzdem ist Addition nicht NP-schwer.
-
Auch wenn ich keine Einschränkungen mache, d.h. ein Spezialfall meines Problem das Knapsack ist?
-
Generell sagt die Tatsache, dass sich allgemein ein Problem auf ein NP-schweres reduzieren lässt, nicht viel aus. Jedes Problem in NP kann man auf ein NP-vollständiges Problem (z.B. SAT) reduzieren, inklusive aller Probleme in P.
Wenn es jetzt um Spezialfälle von Problemen geht, hilft es je nach Definition von Spezialfall nichtmal, wenn der Spezialfall selbst NP-schwer ist. Nimm zum Beispiel das Problem, ob eine aussagenlogische Formel erfüllbar ist oder mindestens 100 Variablen enthält. Man könnte nun sagen, dass SAT ein Spezialfall dieses Problems ist (wenn die Formel weniger als 100 Variablen enthält, muss ich SAT für diese Formel lösen), trotzdem ist das Problem in P, weil SAT über höchstens 100 Variablen asymptotisch konstant lösbar ist.
Es funktioniert aber in anderen Fällen. 3SAT kann man als Spezialfall von SAT auffassen und aus der NP-schwere von 3SAT folgt die NP-schwere von SAT. Das liegt aber daran, weil man 3SAT (trivial) auf SAT reduzieren kann, wenn man also SAT polynomiell lösen könnte, dann auch 3SAT. In dem obigen Beispiel funktioniert das nicht.
Zusammengefasst hast du also vermutlich wenig gewonnen, wenn du einen Spezialfall des Problems auf ein NP-schweres Problem reduzieren kannst, weil das nichts über die Schwere des Spezialfalls aussagt. Wenn der Spezialfall selbst NP-schwer ist, kann das auch für das eigentliche Problem gelten, wenn man den Spezialfall auf das Problem reduzieren kann. Hier kommt es vor allem darauf an, was man als Spezialfall sieht.
-
In meinem Fall habe ich ein Problem, was als Eingabe zwei Mengen mit je a und b Werten bekommt, sowie einen Parameter c.
Wenn ich a=1 und c=1 setze, habe ich das subset sum problem.
Also liegt wohl nahe, dass das für allgemeines a und c wohl auch NP schwer ist, oder?
-
In der Theorie muss man hier noch etwas spitzfindig sein. Wenn a und c Teil der Eingabe sind, dann ja. Denn dann könntest du ja Eingaben mit a=1 und c=1 bekommen, die du nicht effizient lösen kannst. Die Komplexität bezieht sich ja immer auf den worst case. Wenn a und c aber zur Problembeschreibung und nicht zur Eingabe gehören, dann nicht unbedingt. Es könnte sein, dass die Probleme in den Fällen a != 1 oder c != 1 effizient lösbar sind. Und wenn a und c fest sind, dann können die schlimmen Fälle nicht auftreten.
Ich lese aber heraus, dass a und c in deinem Programm variabel sind. In der Praxis bedeutet es somit, dass du zumindest für den allgemeinen Fall vermutlich keinen effizienten Algorithmus finden wirst.
-
...
-
ipsec schrieb:
In der Praxis bedeutet es somit, dass du zumindest für den allgemeinen Fall vermutlich keinen effizienten Algorithmus finden wirst.
In der Theorie findet man keinen effizienten Algorithmus. Praktisch sollte Subset Sum ziemlich schnell zu lösen sein.
-
NP schrieb:
In meinem Fall habe ich ein Problem, was als Eingabe zwei Mengen mit je a und b Werten bekommt, sowie einen Parameter c.
Wenn ich a=1 und c=1 setze, habe ich das subset sum problem.
Also liegt wohl nahe, dass das für allgemeines a und c wohl auch NP schwer ist, oder?Na also, das *ist* doch eine Reduktion von subset sum auf dein Problem: du baust einfach die Instanz und setzt a und c auf 1. zumindes wenn du jede beliebige Instanz von subset sum so darstellen kannst.