NP vollständig

freakC++

Hallo zusammen,

ich halte ein Referat über NP vollständige Probleme und ich hoffe, dass mir jemand weiterhelfen kann. Zwar ist dieses Forum nicht ganz richtig, doch ein besseres gibt es auf dieser Domäne wohl nicht.

Ich weiß, dass ein Problem NP vollständig ist, wenn es zum einen aus der Komplexitätsklasse NP kommt und wenn es "schwierig" ist.

Ich verstehe aber nicht, was ein "schwieriges" Problem ist. Kann mir das jemand umgangssprachlich erklären?

Das wäre sehr nett.

Vielen Dank
lg, freakC++

volkard

"schwierig"

Ich habe ein Problem. Steckt auch viel geld dahinter. Mir fällt leider keine sauschnelle Implemetierung ein. Schlimmer noch, es ist lahm bei mir. Also exponentionentiell lahm.
Jetzt forsche ich mal ein paar Monate daran herum, ob ich das nicht schneller kriege. Dabei versuche ich auch zu beweisen, daß es NP-vollständig ist. Das geht so:
Ich behaupte mal, mein Problem sei schnell lösbar und ich hätte einen Algo dafür gefunden.
Ich überlege mir ein Verfahren, wie ich ein bekanntes NP-vollständiges Problem so transformieren kann, daß ich dann mit meinem schnellen Algo es schnell lösebn kann. Falls ich so eine Übersetzung finde, uih.
Oh, kann ja gar nicht gehen, weil das bekannte NP-vollständige Problem dann gar nicht NP-vollständig war. Also ist meins auch NP-vollständig.

Dann hab ich zwar keinen schnellen Algo. Aber ich darf die Suche dafür im Rahmen meines Softwareprojekts beruhigt aufgeben, denn Heerscharen von schlauen Leuten haben sich daran schon die Zähne ausgebissen.

freakC++

Danke für deine Antwort. Deine Erklärung für NP vollständige Probleme hat mir sehr geholfen. Ich habe noch zwei Fragen:

1.) Ist ein Problem also NP - schwer, wenn es sich auf ein Problem in NP zurückführen lässt?

2.) Das berühmte NP vollständige Problem "Das Problem des Handlungsreisenden" muss ja auch NP - schwer sein, weil es sonst nicht vollständig wäre. Doch auf welches Problem lässt sich dieses zurückführen?

Vielen Dank
lg, freakC++

Tobiking2

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

Beweisen tut man es ungefähr so wie Volkard schon geschrieben hat. Man nimmt ein Problem (formal gesehen alle Probleme) das bewiesenerweise schon NP-Vollständig ist. Nun Versuchen wir eine Lösung für unser Problem so umzuwandeln (in polynomieller Zeit) das es eine Lösung für das NP-Vollständige Problem wird. Gäbe es nun einen Algo, der unser Problem "besser" löst, wäre das NP-Vollständige Problem nicht mehr NP-Vollständig. Das wäre aber ein Wiederspruch, daher kann es so einen Algo nicht geben.

Tobiking2

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.

icarus2

Bis jetzt hat aber noch keiner beweisen können, dass NP vollständige Probleme nicht effizient lösbar sind.

Vielleicht wäre es für dich noch interessant das Tautologieproblem und die Frage der Unerfüllbarkeit anzuschauen. Wie schon geschrieben hat Cook bewiesen, dass alle NP vollständigen Probleme auf die genannten Probleme zurückführen kann. Heisst also: wenn du einen effizienten Algorithmus für die beiden Probleme findest, kannst du alle NP vollständigen Probleme effizient lösen.

volkard

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.
?

SG1

Verstehst Du richtig.

freakC++

Super! Danke Leute. Ihr wart mal wieder sehr hilfreich!

Gute Nacht.

lg, freakC++

icarus2

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 ^^

Zeus

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?!!

Jester

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.

Jester

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.

Jester

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.

volkard

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).

Zeus

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?

Tobiking2

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

Jester

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?

otze

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.

Jester

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.