Lösung des P-NP-Problems?

Zitat von Adok

Also, mir war eigentlich nicht klar, dass gerade dieser eine Schritt derjenige ist, der den Forschern auf der ganzen Welt Kopfzerbrechen bereitet. Aber wenn dem so ist: gut, dann kommt noch einiges an Arbeit auf uns zu, bis P != NP bewiesen ist. Doch, wie gesagt, man müsste erst einmal mit einer Literaturrecherche abklären, ob es nicht doch bereits einen Beweis für diesen einen Schritt gibt, bzw. einen Beweis, dass meine Annahme ungültig ist.

Wie gesagt, so ein Beweis würde P!=NP zeigen. Wenn es ihn gäbe und er zugänglich wäre, dann würde das Clay Institut nicht eine Million auf ihn setzen. Es ist natürlich nicht ausgeschlossen, dass es ihn gibt. Gefunden muss er halt werden ;).

Zitat von Adok

Naja, dieser Beweis würde alleine eben nicht ausreichen: Man muss (wie ich getan habe) auch noch beweisen, dass der Suchraum für ein konkretes NP-Problem eine exponentielle untere Schranke hat

Das ist trivial. Sonst wäre das Problem ja in P.

(Ich finde du solltest Paulchens Rat bezüglich Literaturrecherche annehmen, sonst kommst du leicht in peinliche Situationen.)

Zitat von Adok

Das würde ich nicht so sagen. Wenn man noch nicht bewiesen hat, dass der Suchraum eine exponentielle untere Schranke hat, kann man nicht sagen, dass das Problem in P liegt. Man müsste dazu zeigen, dass die obere Schranke für den Suchraum polynomiell ist.

Entschuldige, damit hast du natürlich recht.

Zitat von Adok

Ich gehe davon aus, dass es keinen Algorithmus geben kann, der das Problem in polynomieller Laufzeit löst, weil der Suchraum (Anzahl der zu untersuchenden Lösungsmöglichkeiten) exponentiell mit der Größe der Eingabedaten (Anzahl der Knoten des Graphen) wächst. Ich beweise, dass der Suchraum tatsächlich exponentiell wächst - dieser Beweis dürfte hieb- und stichfest sein. Was ich nicht beweise, ist, dass es keinen polynomiellen Algorithmus geben kann, wenn der Suchraum exponentiell wächst. Das nehme ich nur an. Wie gesagt, könnte es sein, dass jemand anderer diesen Zusammenhang bewiesen hat. Es könnte auch sein, dass jemand anderer bewiesen hat, dass dieser Zusammenhang nicht besteht - in diesem Fall wäre die Schlussfolgerung P != NP unzulässig. Sollte aber der Zusammenhang beweisbar sein, wäre P != NP die gültige Schlussfolgerung.

Gegenbeispiel:
Anzahl der Spanning Trees auf kompletten Graphen (ie Suchraum) is exponentiell (siehe http://en.wikipedia.org/wiki/Spanning_tree) in Anzahl der Knoten, Minimum Spanning Tree ist in P

Zitat von Adok

Angenommen, ihr glaubt, das P-NP-Problem gelöst zu haben. Was macht ihr dann?

Weiterarbeiten und meinem Glauben keine weitere Beachtung schenken.

edit: oder es zumindest versuchen, was nicht immer so einfach ist

Zitat von Adok

Das ist so ein Fall, wo mit einem Algorithmus in P der Suchraum auf eine polynomielle Zahl (z. B. 1) heruntergebrochen werden kann.

Beim 3-Färbungsproblem kann ich den Suchraum auf jeden Fall auf 2^d (bei n = 4d) herunterbrechen, dieser Wert ist aber exponentiell. Ich kann den Suchraum auch auf eine polynomielle Zahl herunterbrechen, nur bleibt die Frage offen, ob das in polynomieller Zeit möglich ist. Bisher habe ich keinen polynomiellen Algorithmus gefunden.

Du verwendest den Begriff des Suchraums imho komisch ...
Falls du mit "Suchraum" die Anzahl der möglichen Lösungskandidaten für ein Problem meinst, so ergeben deine Aussagen im PDF und hier im Thread keinen Sinn. Falls du damit die Anzahl der Lösungen meinst, die dein Algorithmus durchsuchen muss, so sagst du im Wesentlichen: Wenn es einen in der Laufzeit polynomiell beschränkten Algorithmus für ein NP-vollständiges Problem gibt, so gibt es einen in der Laufzeit polynomiell beschränkten Algorithmus für ein NP-vollständiges Problem.

Sorry, aber auch abgesehen davon strotzt dein PDF nur von Fehlern, generalisierenden oder falschen Annahmen und va Halbwissen (von der Beweisstruktur etc gar nicht zu reden), dass man gar nicht auf alle eingehen kann... (Literaturrecherche ist echt kein schlechter Tipp, möchtest du dich einmal wirklich ernsthaft mit dem P=NP Problem beschäftigen)

Nur eine Anmerkung zur P=NP?-Problematik:

Du schreibst in deinem PDF folgendes:

Zitat

Dagegen ist einzuwenden, dass es ja exponentiell viele Permutationen gibt und man
im schlimmsten Fall fast alle durchprobieren müsste, bis man auf eine stoßen würde,
bei denen diese Lösungsmöglichkeiten gültig wären.

Bei der Frage P=NP geht es jedoch - jetzt bewusst salopp und untechnisch formuliert - genau um die Frage, ob man bei NP-vollständigen Problemen den exponentiell großen Suchraum im Worst Case immer komplett durchsuchen muss oder ob es trotz exponentiell großen Suchraums einen Algorithmus gibt, der auch (und gerade) im Worst Case nicht alle Möglichkeiten enumerieren muss, um das Problem exakt zu lösen.

Es gibt viele Probleme mit exponentiell vielen möglichen Lösungskandidaten (i.e. Suchraum), für welche trotzdem polynomielle Lösungsalgorithmen existieren. m4rs hat dir schon eines genannt. Selbst das Shortest Path - Problem hat exponentiell großen Suchraum, ist aber mit polynomiellen Algorithmen effizient und schnell lösbar.
Stell dir nun zB vor, ein genialer Graphentheoretiker findet / entwickelt graphentheoretische Lemmata und Sätze, welche die Grundlage für einen polynomiellen Algorithmus zum 3-Färbungsproblems sein können (analog zu zB Eulerschen Pfaden) - schon musst du nicht mehr zwingend alle Lösungskandidaten durchgehen. (davon abgesehen hätte der geniale Graphentheoretiker hiermit nebenbei indirekt auch P=NP bewiesen)

So und nun um deine Frage auch zu beantworten:

Zitat

Angenommen, ihr glaubt, das P-NP-Problem gelöst zu haben. Was macht ihr dann?

Sollte ich P =/= NP bewiesen haben - meine Million Dollar, ewigwährenden Ru(h)m und Professorenstelle an Uni meiner Wahl einfordern.
Sollte ich P = NP bewiesen haben - ausnutzen, dass ich der einzige bin, der NP-vollständige Probleme (e.g. Primfaktorenzerlegung ) effizient lösen kann und etwas später oben genannte Dinge einfordern.

/offtopic

Weil's zum Thema passt:
Wer von euch hat zufällig schon den Film Travelling Salesman gesehen?

Zitat von Adok

polynomielle Zahl [...] herunterbrechen

Du verwendest Begriffe, die sonst niemand verwendet, und definierst sie nicht. Das macht deine Beweisversuche wertlos.

Zitat von master_fluc

Wer von euch hat zufällig schon den Film Travelling Salesman gesehen?

Ich nicht, aber OMG, da sollte jemand ein Screening auf der TU veranstalten.

Zitat von master_fluc

ewigwährenden Ru(h)m

Ja.. ewigwährender Rum wäre etwas Schönes.. :inlove:

Zitat von master_fluc

Weil's zum Thema passt:
Wer von euch hat zufällig schon den Film Travelling Salesman gesehen?

Nein. Aber falls du (oder wer anderer hier) ihn schon gesehen hat.. werden die Begriffe darin "richtig" verwendet, oder ist das wieder so ein Hollywood-OMG_ER_HAT_DAS_INTERNET_GEHACKT-ähnlicher Film?

Zitat von Adok

Zum Suchraum:
Es geht darum, ob man unbedingt exponentiell viele Lösungskandidaten untersuchen muss, um mit einem (in polynomieller Zeit ablaufenden) Algorithmus die richtige Lösung finden zu können. Beim Shortest-Path-Problem zum Beispiel gibt es natürlich exponentiell viele Lösungskandidaten, aber man muss nicht unbedingt exponentiell viele Lösungskandidaten untersuchen, um die richtige Lösung zu finden.

Ich glaube es ging rein um die Unterscheidung zwischen "Lösungsraum" und "Suchraum". Lösungsraum ist der Raum aller möglichen Lösungen. Suchraum ist der Raum, der von einem Algorithmus durchsucht wird (zumindest habe ich das so in Erinnerung - korrigiert mich wer, wenn ich falsch liege).

Zitat von Adok

Solche Aussagen habe ich besonders gern. Mit einer solchen Aussage stellst du dich nämlich über mich und behauptest, dass du etwas Besseres bist, ohne aber darauf einzugehen, was konkret falsch ist. Man kann dir Glauben schenken oder auch nicht. In der Vergangenheit ist es in ähnlichen Fällen schon vorgekommen, dass derjenige, der Ähnliches behauptet hat, auf nähere Nachfrage nur einige wenige Punkte nennen konnte, die falsch waren, also die Aussage "der Text strotzt von Fehlern" eine maßlose Übertreibung war.

Zugegeben: Ich fand die Antwort zwar auch relativ polemisch (vor allem auch, weil die Kernaussage bereits in Posting #8 getroffen wurde).. ich denke aber, dass das vor allem von der Art und Weise herrührt, wie du auf Kritik reagierst.
Du scheinst zuerst generell davon auszugehen, dass andere Leute falsch liegen. Du triffst dabei auch Aussagen, die extrem überheblich wirken. Wenn dir vor Augen gehalten wird, dass deine Idee so nicht funktioniert, reagierst du ablehnend. Kritik (wenn auch von manchen - und da schließe ich mich nicht aus - oft polemisch rübergebracht) scheinst du einfach zu ignorieren, auch wenn du schon siehst, dass du falsch liegst.
Du willst, dass sich die Leute vier A4-Seiten "Beweis" durchlesen, und reagierst, nachdem dein "Beweis" widerlegt wurde auf den Hinweis, dass du vielleicht zuerstmal Literaturrecherche betreiben könntest mit "Dazu bin ich zu faul ;)". Du stößt damit Leute einfach so vor den Kopf, die sich Zeit nehmen, um sich dein Schriftstück durchzulesen, um dir zu helfen, indem sie dir Feedback geben. Findest du das fair? Ist das nicht überheblich? Ich hab's zwar (auch dank Steinhardt) nicht so mit Ethik.. Aber sagt dir "Was du nicht willst, dass man dir tu', das füg' auch keinem anderen zu." was?
Aus meiner Sicht ist der raue Wind, der dir hier teilweise entgegenschlägt, großteils selbst verschuldet. Ich für meinen Teil würde es schön finden, wenn du die Ratschläge, die du anderen gibst, auch selbst beherzigst.

Dass das jetzt selbst arrogant rüberkommt, kann sein. Gedacht ist es aber nur als gut gemeinter Ratschlag.

Liebe Grüße
emptyvi

Zitat von Adok

Solche Aussagen habe ich besonders gern. Mit einer solchen Aussage stellst du dich nämlich über mich und behauptest, dass du etwas Besseres bist, ohne aber darauf einzugehen, was konkret falsch ist. Man kann dir Glauben schenken oder auch nicht. In der Vergangenheit ist es in ähnlichen Fällen schon vorgekommen, dass derjenige, der Ähnliches behauptet hat, auf nähere Nachfrage nur einige wenige Punkte nennen konnte, die falsch waren, also die Aussage "der Text strotzt von Fehlern" eine maßlose Übertreibung war.

Ich habe mich mit meinem Posting in keinster Weise "über dich gestellt" oder auch nur ansatzweise derartiges behauptet. Das Feedback bezog sich auch nicht auf dich, sondern auf deinen "Beweis". Wenn du da nicht unterscheiden und damit nicht umgehen kannst, ist das dein Problem.

Dein "Beweis" ist Hand-Waving par excellence...

Um dir auch ein paar Beispiele für Ungenauigkeiten, Halbwahrheiten und Fehlern in deinen Annahmen zu geben (alles aus einem einzigen Absatz - bei weitem kein Anspruch auf Vollständigkeit):

Zitat

Die theoretische Grundlage hinter P und NP sind hierbei die so genannten Turing-Maschinen

Dieser Satz ist schlicht falsch. Turing-Maschinen sind ein theoretisches mathematisches Berechenbarkeits-Modell. Mit diesem Modell kann zwar die P/NP Thematik beschrieben werden, Turing Maschinen sind aber weder die "Grundlage" hinter P und NP, noch bei weitem nicht die einzige Möglichkeit, sich der P/NP Thematik anzunähern oder diese mathematisch zu beschreiben.
Das meinte ich mit Halbwissen.

Zitat

Eine Turing-Maschine ist ein einfacher Apparat, der in der Lage ist, genau jene Probleme zu lösen, die auch ein Computer zu lösen imstande ist.

Wenn der Satz stimmen würde, wäre die Frage, ob P=NP ist oder nicht, nur in der Theorie relevant. Gäbe es Computer, welche Instanzen einer nichtdeterministischen Turing-Maschine darstellen, so könnten wir jedes NP-vollständige Problem in polynomieller Zeit lösen.
Bis Quanten-Computer in die Läden kommen, wird es aber noch etwas dauern...

Zitat

Formal sind P und NP nun so definiert: Jedes Problem, das in P liegt, kann von einer deterministischen Turing-Maschine in polynomieller Zeit gelöst werden; und jedes Problem, das in NP liegt, kann von einer nichtdeterministischen Turing-Maschine in polynomieller Zeit gelöst werden.

Formale Definition ist das aber keine und daneben auch ungenau. Um die Definition etwas zu formalisieren:
Ein Problem X liegt in P, wenn für dessen Lösung ein Algorithmus existiert, der alle Instanzen dieses Problems auf einer deterministischen Turing-Maschine korrekt lösen kann und dessen Laufzeit im Worst-Case für alle Instanzen in der Laufzeit polynomiell beschränkt ist.
Zumindest drei Ergänzungen, um deine "Definition" wirklich etwas zu formalisieren.

Zitat

Es lässt sich aber jede nichtdeterministische Turing-Maschine, die eine polynomielle Laufzeit aufweist, in eine deterministische Turing-Maschine umwandeln, deren Laufzeit exponentiell ist.

Der Satz ergibt so keinen Sinn und ist daneben auch falsch. Du schreibst weder, dass diese Aussage nur hinsichtlich eines bestimmten Problems stimmen kann und auch nur hinsichtlich der Worst-Case Laufzeit.

Die restlichen Dinge kannst du dir selbst raussuchen, wenn du dich in die Materie mal eingelesen hast.
Und komm jetzt nicht mit "das habe ich ja alles anders gemeint". Wenn du es anders meinst, dann musst du es in einem Beweis, der sich anmaßt, die P/NP Frage zu lösen, auch hinschreiben.

Zum Schluss noch ganz allgemein zum Beweis - nur weil du es nicht geschafft hast, für ein (!) NP-vollständiges Problem auf drei Seiten einen polynomiellen Algorithmus zu finden, bedeutet das nicht, dass du die Frage P=NP gelöst hast.

Ein gut gemeinter Tipp: Versuche bei zukünftigen Beweisen Ungenauigkeiten und Halbwissen zu vermeiden, definier' Dinge auf formale Weise und ziehe daraus formale Schlüsse (mittels Beweisen), vielleicht wird's dann was mit der Lösung von P=NP.

Zitat von Adok

Zum Suchraum:
Es geht darum, ob man unbedingt exponentiell viele Lösungskandidaten untersuchen muss, um mit einem (in polynomieller Zeit ablaufenden) Algorithmus die richtige Lösung finden zu können.

Dass diese Aussage eine Tautologie ist, ist dir aber schon klar?

Zitat von emptyvi

Aber falls du (oder wer anderer hier) ihn schon gesehen hat.. werden die Begriffe darin "richtig" verwendet, oder ist das wieder so ein Hollywood-OMG_ER_HAT_DAS_INTERNET_GEHACKT-ähnlicher Film?

Nein, leider noch nicht. Hoffentlich kommt bald ein Screening in unsere Gegend.

Zitat von Adok

Verwechselst du da nicht Berechenbarkeit und Komplexität?

Nein, aber jetzt weiß ich, wie du diesen Satz gemeint hast. Ich hatte in diesem Kontext nicht mit Berechenbarkeit gerechnet, sondern den Satz so verstanden, dass gemeint war, jeder Computer könnte eine nichtdeterministische Turing-Maschine simulieren und somit Probleme in polynomieller Zeit lösen.

Zitat von Adok

Eh nicht. Aber wenn es mir gelingen könnte zu beweisen, dass es keinen polynomiellen Algorithmus für ein bestimmtes NP-vollständiges Problem geben kann, wäre P=NP gelöst. Aber das habe ich nicht bewiesen.

Dieser Negativ-Beweis ist allerdings schwer zu führen, aber solltest du es schaffen, ist dir die Million sicher.

Zitat von Adok

Wenn ich eine Aussage in eine andere Aussage umformen kann, wobei beide Aussagen zueinander logisch äquivalent sind, kann ich dennoch neue Erkenntnisse gewinnen. Also sind Tautologien nicht grundsätzlich nutzlos.

Naja .. in diesem Kontext ist aber nicht viel damit gewonnen, wenn die Anzahl der Möglichkeiten, die der Algorithmus durchsuchen muss polynomiell ist, ist klar, dass dieser Algorithmus polynomielle Laufzeit hat. Interessant wird es dann, wenn die Anzahl der möglichen Lösungen exponentiell bleibt und der Lösungs-Algorithmus trotzdem polynomielle Laufzeit hat.
Und genau darauf läuft die P=NP Problematik schlussendlich raus: Muss ich alle möglichen (exponentiell viele) Lösungen eine nach der anderen durchgehen (also exakte Enumeration als einzige Lösungsmethode), um das Problem zu lösen (dann P=/=NP) oder geht es nicht doch schneller (dann P=NP)?

Hier ~ 100 "Beweise" zum Thema:

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Zitat

Note: The following paragraphs list many papers that try to contribute to the P-versus-NP question. Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community: The paper by Mihalis Yannakakis. (And this paper does not settle the P-versus-NP question, but "just" shows that a certain approach to settling this question will never work out.

Zitat von Adok

Ich hätte gedacht, dass die Probleme, die in P sind, jedenfalls erlauben, den Suchraum auf eine polynomielle Anzahl von Lösungen zu begrenzen, und das in polynomieller Zeit (wichtig!). Sei es auch nur, dass der Algorithmus in polynomieller Zeit die richtige Lösung findet - das ist ja auch nur ein Spezialfall dieses Ansatzes.

Der Suchraum muss aber nicht "begrenzt" werden (was auch immer du damit meinst), es kommt darauf an, dass der Algorithmus auch im Worst Case polynomiell in der Laufzeit beschränkt ist.
Dass eine polynomielle Anzahl an potentiellen Lösungskandidaten maximal polynomielle Laufzeit zur Lösung erfordert, ist trivial.