NP vollständig
-
Super! Danke Leute. Ihr wart mal wieder sehr hilfreich!
Gute Nacht.
lg, freakC++
-
Ja, das verstehst du richtig.
Das hat zumindest unser Professor in Diskreter Mathematik gesagt. Wir konnten natürlich den Beweis dazu nicht führen... nicht genug Zeit und ziemlich sicher auch zu schwierig für 1. Semester Studenten ^^
*Edit
War wohl mal wieder etwas langsam ^^
-
volkard schrieb:
icarus2 schrieb:
Bis jetzt hat aber noch keiner beweisen können, dass NP vollständige Probleme nicht effizient lösbar sind.
Verstehe ich das dann richtig so:
"NP-vollständig" steht für eine Menge von Problemen, die allesamt irgendwie "schwierig" sind. Von ihnen vermutet man, daß sie nicht in polynomialer Laufzeit lösbar sind.
Falls es für eins der Probleme gelingt, zu beweisen, daß es nicht in polynomialer Laufzeit lösbar ist, ist das auch automatisch für die anderen bewiesen.
Falls es für eins der Probleme gelingt, zu beweisen, daß es doch in polynomialer Laufzeit lösbar ist, ist das auch automatisch für die anderen bewiesen.
?Irgendwie kommt mir das spanisch vor. Mal sehen, ob es verbal Probleme macht oder ich einfach schlecht in Theorie bin.
Ich gebe mal eine "kleine" Menge von Probleme an:
P = {TSP und Sortieren}Nun da wir wissen, dass Sortieren richtig effizient lösbar sind, können wir ableiten, dass das Problem nicht NP-vollständig ist. Oder? Was können wir mit diese Erkenntnis über unsern TSP sagen? TSP ist doch NP-vollständig?!!
-
Tobiking2 schrieb:
Aussage: Problem liegt in NP <=> Es gibt einen Algo für dieses Problem der in NP liegt
Noch offene Frage: Gibt es einen "besseren"?Aussage: Problem ist NP schwer <=> Es gibt keinen Algo der "besser" als NP ist
Noch offene Frage: Gibt es einen Algo in NP oder ist das Problem sogar noch schwerer?Beide Aussagen zusammen: Problem ist NP-vollständig <=> Der "beste" Algo liegt in NP
P und NP sind Problemklassen. Algorithmen sind keine Probleme und liegen damit nicht in diesen Klassen. Aussagen wie "Der Algorithmus liegt in NP" sind also Unsinn.
-
Tobiking2 schrieb:
freakC++ schrieb:
Doch auf welches Problem lässt sich dieses zurückführen?
Es wird in der Regel SAT genommen, das über den Satz von Cook (http://de.wikipedia.org/wiki/Satz_von_Cook) als NP-Vollständig bewiesen wurde. Ich glaub es gab mit der Zeit auch andere Probleme, die nicht über die Redkuktion auf andere Probleme als NP-Vollständig bewiesen wurden, da fallen mir aber gerade keine ein.
Es ist genau umgekehrt! Man führt nicht das Problem, das man untersucht auf ein schon bekanntes zurück, sondern geht umgekehrt vor. Man führt ein Problem von dem man schon weiß das es NP-schwer ist auf das Problem, das man untersuchen möchte zurück. Für TSP gibt es AFAIK eine Reduktion von 3SAT.
-
Zeus schrieb:
volkard schrieb:
icarus2 schrieb:
Bis jetzt hat aber noch keiner beweisen können, dass NP vollständige Probleme nicht effizient lösbar sind.
Verstehe ich das dann richtig so:
"NP-vollständig" steht für eine Menge von Problemen, die allesamt irgendwie "schwierig" sind. Von ihnen vermutet man, daß sie nicht in polynomialer Laufzeit lösbar sind.
Falls es für eins der Probleme gelingt, zu beweisen, daß es nicht in polynomialer Laufzeit lösbar ist, ist das auch automatisch für die anderen bewiesen.
Falls es für eins der Probleme gelingt, zu beweisen, daß es doch in polynomialer Laufzeit lösbar ist, ist das auch automatisch für die anderen bewiesen.
?Irgendwie kommt mir das spanisch vor. Mal sehen, ob es verbal Probleme macht oder ich einfach schlecht in Theorie bin.
Ich gebe mal eine "kleine" Menge von Probleme an:
P = {TSP und Sortieren}Nun da wir wissen, dass Sortieren richtig effizient lösbar sind, können wir ableiten, dass das Problem nicht NP-vollständig ist. Oder? Was können wir mit diese Erkenntnis über unsern TSP sagen? TSP ist doch NP-vollständig?!!
Deine Menge P ist aber nicht die Menge der NP-vollständigen Probleme. Volkards Aussage gilt ja nicht für jede beliebige Menge von Problemen, sondern nur die Menge der NP-vollständigen Probleme. Die wird manchmal auch mit NPC bezeichnet.
-
freakC++ schrieb:
1.) Ist ein Problem also NP - schwer, wenn es sich auf ein Problem in NP zurückführen lässt?
Siehe Posting zwei über mir (08 Nov 2010 22:52).
-
Jester schrieb:
Zeus schrieb:
....
Deine Menge P ist aber nicht die Menge der NP-vollständigen Probleme. Volkards Aussage gilt ja nicht für jede beliebige Menge von Problemen, sondern nur die Menge der NP-vollständigen Probleme. Die wird manchmal auch mit NPC bezeichnet.
Und wie hilft mir mein TSP-Beweis beim N-Puzzel-Problem?
-
Wenn du dir TSP und Sortieren anguckst, müsstest du versuchen aus dem Ergebnis der Sortierung in polynomieller Zeit eine Lösung für TSP zu bauen. Ich behaupte einfach mal das eine Sortieren z.B. nach Entfernungen bei TSP relativ wenig bringt.
Ein Beispiel das ich gerade im Kopf habe ist 3-SAT (Speziallfall von SAT mit nur 3 Literalen pro Klausel, das ebenfalls NP-Vollständig ist) und 3-Col. 3-Col ist das Problem auf einer Karte die Gebiete mit 3 Farben so einzufärben, dass nie 2 mal die gleiche Farbe in benachbarte Gebiete anliegt. Formal kann man da einen Graphen draus machen, Gebiete = Knoten und benachbarte Gebiete sind mit einer Kante verbunden. Man kann nun relativ mühsam beweisen, dass man zu jeder 3-SAT Formel einen solchen Graphen in polynomieller Zeit konstruieren kann, und eine Färbung dieses Graphen auch eine erfüllende Formel der 3-SAT Formel erzeugt.
Damit ist 3-Col auch NP-Vollständig, und gäbe es einen Algorithmus der diese Färbung effizient berechnet, dann wäre der Algo (Graph erzeugen, Färbung berechnen, Ergebnis zurückwandeln) ebenfalls effizient.
Wobei man natürlich bedenken muss das effizient hier nur allgemein polynomielle Laufzeit bedeutet. Laufzeiten wie O(n^1000000) sind aus praktischer Sicht weit von effizient weg, sind aber noch polynomiell
-
Zeus schrieb:
Und wie hilft mir mein TSP-Beweis beim N-Puzzel-Problem?
Kannst Du ein bißchen mehr Kontext liefern? Ich verstehe die Frage nicht. Was ist "Dein TSP-Beweis" und was beweist der? Und was ist das N-Puzzel-Problem?
-
Zeus schrieb:
Und wie hilft mir mein TSP-Beweis beim N-Puzzel-Problem?
Wenn du eine Funktion findest, die jede Eingabe des N-Puzzle so auf das TSP abbildet, dass die Rücktransformierte TSP-Lösung eine Lösung des N-Puzzle liefert und die Abbildung selbst polynomiell ist, dann hast du bewiesen, dass N-Puzzle NP-vollständig ist.
In dem Moment, wo jemand eine schnelle Lösung für das TSP findet, kannst du dann automatisch N-Puzzle polynomiel schnell lösen, weil du die richtige Abbildung ja bereits kennst.
-
otze schrieb:
Zeus schrieb:
Und wie hilft mir mein TSP-Beweis beim N-Puzzel-Problem?
Wenn du eine Funktion findest, die jede Eingabe des N-Puzzle so auf das TSP abbildet, dass die Rücktransformierte TSP-Lösung eine Lösung des N-Puzzle liefert und die Abbildung selbst polynomiell ist, dann hast du bewiesen, dass N-Puzzle NP-vollständig ist.
Nein, andersrum! Du mußt jede Instanz des TSP-Problems in polynomieller Zeit in ein N-Puzzel überführen um die NP-vollständigkeit von N-Puzzle zu zeigen! Wenn danach jemand TSP löst hilft Dir das erstmal nichts, weil Deine Reduktion in der anderen Richtung geht. Genau das ist ja auch der Sinn der Sache, Du willst ja zeigen wer Dein Problem (N-Puzzel) löst, der löst auch TSP... und deswegen isses schwer.
-
Ist es "üblich", daß man wenn man sorum eine Überführung findet, dann auch ein paar Monate später jemand andersrum eine Reduzierung findet?
-
Nein, das ist nicht üblich. Man zeigt üblicherweise (bzw. versucht zu zeigen) dass das Problem in NP ist. Das könnte man tun, indem man es auf ein geeignetes Problem aus NP zurückführt. Aber oft ist es einfacher mit einer äquivalenten Definition von NP zu Arbeiten, nämlich der dass NP alle Probleme enthält für die eine gegebene Lösung in polynomieller Zeit überprüft werden kann -- und genau das zeigt man. Das ist meistens sehr einfach... im Falle von TSP gebe ich Dir eine Tour und behaupte sie habe Länge höchstens k. Du prüfst also nur, ob es eine Tour ist und ob deren Länge höchstens k ist. Das ist ganz leicht in polynomieller Zeit zu bewerkstelligen.
Dadurch weiß man dass das Problem in NP ist weiß man also, dass es sich in polynomieller Zeit in jedes beliebige NP-vollständige Problem transformieren lässt. Eine konkrete Transformation ist dann meist uninteressant. Überhaupt wird die Zugehörigkeit zu NP meist nur sehr knapp behandelt, weil das in den meisten Fällen (wie zuvor skizziert) ziemlich simpel ist. Es gibt allerdings auch einige hartnäckige Fälle von denen man immer noch nicht weiß ob sie zu NP gehören. Da wäre ein Fortschritt sicher gerne gesehen.