StartseiteMathlog

Ein Gegenbeispiel zu P=NP?

Von / 15. August 2017 / 61 Kommentare
Mehr

Das P=NP-Problem ist der heilige Gral der theoretischen Informatik, auf seine Lösung hat das Clay-Institut ein Preisgeld von 1 Million Dollar ausgesetzt. Es fragt, ob jedes von einer nichtdeterministischen Turingmaschine in polynomieller Zeit lösbare Problem auch von einer deterministischen Turingmaschine in polynomieller Zeit gelöst werden kann.
Ein gestern von Norbert Blum, Informatikprofessor an der Universität Bonn, auf dem ArXiv archivierter Preprint “A solution of the P versus NP Problem” will nun beweisen, dass ein gewisses Problem nicht in polynomieller Zeit gelöst werden kann und demzufolge P\not= NP ist.
Auf cstheory.stackexchange (und wahrscheinlich bald auch an anderen Orten) wird der Beweis bereits kontrovers diskutiert.

Nachtrag (2.9.): Herr Blum hat am 30.8. seinen Beweis zurückgezogen. Eine genauere Analyse soll später auf seiner Webseite erscheinen.

Stichworte: , , ,
Mehr

Kommentare (61)

  1. #1 Bodo
    15. August 2017

    Ist das Gegenbeispiel zum Gegenbeispiel dann der Grund, weshalb man spätestens ab der Folge, wo man erfährt, dass Sheldon einen Zeitreisebeweis als “enttäuschend” ansieht, in Team “Sheldon und Penny” sein sollte?

  2. #2 Karl-Heinz
    16. August 2017

    P und NP – Für Laien erklärt.
    Bezieht sich jetzt wohl nicht auf den aktuellen Beweis, aber das worum es geht, ist sehr einfach erklärt.
    https://nkblog.nkdev.de/p-und-np-fur-laien-erklart/

  3. #3 Karl-Heinz
    16. August 2017

    Hat ein Bonner Professor das größte Rätsel der Informatik gelöst?

    https://www.spektrum.de/news/loesung-fuer-p-np-problem/1494941

  4. #4 Karl-Heinz
    16. August 2017

    Das wusste ich nicht, dass der Primzahltest zur Komplexitätsklasse P gehört.

    AKS-Primzahltest
    https://de.m.wikipedia.org/wiki/AKS-Primzahltest

  5. #5 schlappohr
    16. August 2017

    Ich bin wirklich gespannt, ob der Beweis stimmt. Aber falls nicht, müsste man sich angesichts der vielen gescheiterten Beweise die Frage stellen, ob das Problem P==NP überhaupt entscheidbar ist.

  6. #6 Karl-Heinz
    16. August 2017

    @schlappohr

    NP-vollständig Problen sind aber entscheidbar.

  7. #7 Karl-Heinz
    16. August 2017

    @schlappohr

    NP-vollständig Probleme sind aber entscheidbar.

  8. #8 Karl-Heinz
    16. August 2017

    @schlappohr

    Marquès und Spinoza beweisen, dass die Unentscheidbarkeit der Unentscheidbarkeit der Unentscheidbarkeit der Unentscheidbarkeit des P = NP?-Problems unentscheidbar ist.

  11. #11 Schlappohr
    17. August 2017

    @Karl-Heinz

    Ich gebe zu, dass ich Dir nicht ganz folgen kann. Spinoza lebte im 17.Jahrhundert (?) und ich bezweifle, dass er sich mit Komplexitätstheorie beschäftigt hat. Aber vermutlich weißt Du darüber mehr als ich.

  13. #13 Karl-Heinz
    17. August 2017

    @schlappohr

    Diesen Satz habe ich aus Professor Stewarts mathematische Schätze und ist so glaube ich mehr als Scherz gedacht. Vergleichbar mit dem, ich setze P=0 und behaupte P=NP? sei damit gelöst.

  14. #14 demolog
    17. August 2017

    Für mich ist die Sache eigentlich ziemlich klar:

    Man kann die “Nichtsexistenz” formal gar nicht beweisen.
    Man kann nur beweisen, was tatsächlich existiert.

    Demnach wäre die Lösung dieses P=NP-Problems nur möglich, wenn man beweist, dass es so ist. Falls man keinen Beweis dafür findet, heisst es aber nicht, das N nicht gleich NP sei.

  15. #15 Tox
    18. August 2017

    @demolog:
    Selbstverständlich kann man für bestimmte mathematische Objekte deren Nichtexistenz formal beweisen. Beispielsweise ist es sehr einfach formal zu beweisen, dass es keine rationale Zahl gibt deren Quadrat gleich 2 ist.

  16. #16 demolog
    18. August 2017

    Tox
    18. August 2017 #15

    Ihr Beispiel scheint mir eher unterkomplex zu sein.

    Meine Aussage erstreckt sich nicht über Mathematik allein. Sie ist umfassend gültig – und ist unausgesprochen wissenschaftliche Prämisse, da eine formale Nichtlösbarkeit besteht. Formallogisch kann das “Nichtexistente” nicht (objektiv genug) bewiesen werden.

  17. #17 Tox
    18. August 2017

    @demolog:

    Ihr Beispiel scheint mir eher unterkomplex zu sein.

    Das ist eine übliche Vorgehensweise in der Mathematik. Zur Widerlegung einer falschen Aussage gibt man ein möglichst einfaches Gegenbeispiel an. Wenn Ihre Aussage schon in einem derart simplen Fall nicht zutrifft, kann sie ja kaum allgemein gültig sein.

    Meine Aussage erstreckt sich nicht über Mathematik allein. Sie ist umfassend gültig…

    Wie mein simples Gegenbeispiel zeigt, ist sie in der Mathematik offenbar nicht gültig.

  18. #18 demolog
    18. August 2017

    @ Tox
    18. August 2017

    Sehr witzig. 1+1 ist auch nicht 3. Oder “nicht nicht 2”.

    Ein solcher Beweis gilt nur innerhalb der strengen Regeln des Systems als gültig.
    Darüber hinaus glaube ich an die Mathematik, die mit ihren Anforderungen wächst und Probleme lösst, wenn Lösungen notwendig sind.
    Meint: gegenwärtig gültige Beweise einer Unmöglichkeit könnten einst durch Erweiterung der mathematischen Möglichkeiten widerlegt werden. Jede Wissenschaft wächst an seinen Anforderungen – wenn sie den Prämissen redlich folgt.

  19. #19 Tox
    18. August 2017

    @demolog:
    Das war nicht witzig gemeint. Ich bin einfach der Auffassung, dass Ihre Behauptung falsch ist.

    Ein solcher Beweis gilt nur innerhalb der strengen Regeln des Systems als gültig.

    Selbstverständlich. Ich habe nie gegenteiliges behauptet. Auch ein Beweis von P=NP oder P≠NP wird nur innerhalb des formalen Systems gelten, in dem diese Aussagen formuliert sind. Aber das mindert nicht den Wert eines solchen Beweises.

    Darüber hinaus glaube ich an die Mathematik, die mit ihren Anforderungen wächst und Probleme lösst, wenn Lösungen notwendig sind.

    Sind Sie also der Meinung, dass man irgendwann eine rationale Zahl finden wird, deren Quadrat gleich 2 ist?

  20. #20 demolog
    18. August 2017

    Zitat:
    Sind Sie also der Meinung, dass man irgendwann eine rationale Zahl finden wird, deren Quadrat gleich 2 ist?

    -> Womöglich braucht es das nicht. Sollte es erforderlich sein, erweitert man das System, sodass man ein Zahlensystem hat, welches das leisten kann.

    So funktioniert Mathematik.

    Sie versuchen mir mit einem unterkomplexen Problembeweis zu erklären, wieso eine überkomplex konstruierte Problemfrage negativ entscheidbar sei.

    Die Idee dabei: das konstistente System der Mathematik.
    Doch ob die gegenwärtige Mathematik das P=NP Problem bewältigen kann, steht noch aus. Warum versuchen sie mir Pessismusmus zu unterstellen?
    Die zugrunde gelegte formale Logik ist dagegen eigentlich optimistisch – was sie nicht erkennen.

    Den Grund, warum ihr Beispiel meine Aussage nicht widerlegt, kann ich gerade nicht nennen. Aber es gibt ihn wahrscheinlich.

  21. #21 Tox
    18. August 2017

    @demolog:

    Womöglich braucht es das nicht. Sollte es erforderlich sein, erweitert man das System, sodass man ein Zahlensystem hat, welches das leisten kann.

    Das ist keine Antwort auf meine Frage. Daher nochmal: Halten Sie es grundsätzlich für möglich, dass man irgendwann eine rationale Zahl findet, deren Quadrat gleich 2 ist?

    Sie versuchen mir mit einem unterkomplexen Problembeweis zu erklären, wieso eine überkomplex konstruierte Problemfrage negativ entscheidbar sei.

    Nein, das tue ich nicht. Ich versuche Ihnen lediglich darzulegen, dass Ihre Behauptung aus Kommentar #14 schon im Ansatz falsch ist. (Nur als Randbemerkung zum Thema “unter/überkomplex”: Glauben Sie ernsthaft, eine Frage, die die theoretische Informatik seit über 40 Jahren untersucht, in vier knappen Sätzen entscheiden zu können?)

    Warum versuchen sie mir Pessismusmus zu unterstellen?

    Auch das tue ich nicht.

    Den Grund, warum ihr Beispiel meine Aussage nicht widerlegt, kann ich gerade nicht nennen. Aber es gibt ihn wahrscheinlich.

    Nochmal in kurz: Der Ausgangspunkt Ihrer Argumentation in Kommentar #14 ist Ihre Behauptung, dass es keine formalen Nichtexistenzbeweise geben kann. In Kommentar #15 gebe ich Ihnen ein simples Beispiel eines formalen Nichtexistenzbeweises.

    Wenn Sie ernsthaft der Meinung sind, P vs. NP gelöst zu haben, sollten Sie darauf eine bessere Antwort als “es gibt wahrscheinlich einen Grund” haben.

  22. #22 erik||e oder wie auch immer . . . ..
    18. August 2017

    .. . . . Das Nichtexistente ist nicht beweisbar, weil der Beweis von Nichtexistentem dessen Zustand zerstört, da ich ihm einen Formalismus entgegen setze und dem Nichtexistentem eine Existenz verpasse . . . ..
    . . . .. aus meiner Sicht ist das kein P-NP-Problem . . . ..
    . . . .. P=NP wenn Entscheidungen keinem Zufall unterworfen sind . . . .. da werden Ideologen immer Haare in der Suppe finden . . . .. Haare lassen sich immer finden, um diese in die Suppe zu werfen . . . ..

  23. #23 Tox
    18. August 2017

    Das Nichtexistente ist nicht beweisbar, weil …

    Es geht nicht darum, Nichtexistentes zu beweisen. Es geht um Beweise der Nichtexistenz von Objekten mit gewissen Eigenschaften.

    P=NP wenn Entscheidungen keinem Zufall unterworfen sind

    So so. Dann ist es doch sicherlich ein Leichtes für Sie, einen Polynomialzeitalgorithmus für 3-SAT anzugeben, nicht wahr? 3-SAT liegt bekanntlich in NP, und ob eine gegebene aussagenlogische Formel erfüllbar ist, ist nicht dem Zufall unterworfen.

  24. #24 erik||e oder wie auch immer . . . ..
    18. August 2017

    @Tox
    Worin sehen Sie eine Differenz zu meiner Aussage? Ich kann keine entdecken.

  25. #25 Tox
    19. August 2017

    Beweisen oder Widerlegen kann man nur Aussagen. Und diese existieren dann offensichtlich. In einem Nichtexistenzbeweis beweist man eine Aussage, die besagt, dass ein (anderes) Objekt mit gewissen Eigenschaften nicht existiert. Dieses andere Objekt ist (oder wäre, falls es existierte) im Allgemeinen keine Aussage. Davon zu sprechen, dieses Objekt zu beweisen, ist im Allgemeinen daher unsinning, da man wie gesagt nur Aussagen beweisen kann.

    In meinem Beispiel aus Kommentar #15:

    Sei A die Aussage “Es gibt keine rationale Zahl x, die x² = 2 erfüllt.”. Dann gibt es einen ziemlich einfachen Beweis dieser Aussage. A ist also beweisbar. Und A existiert offensichtlich auch.

    A besagt, dass x ∈ ℚ mit x²=2 nicht existiert. D.h. das Objekt dessen Existenz/Nichtexistenz betrachtet wird, ist (oder wäre, falls es existierte) eine rationale Zahl.

  26. #26 erik||e oder wie auch immer . . . ..
    19. August 2017

    . . . .. kein Widerspruch meinerseits 🙂

  27. #27 Tox
    19. August 2017

    Ergo, Ihr Satz

    Das Nichtexistente ist nicht beweisbar …

    ist nicht sinnvoll? (Da es, wie ich in Kommentar #23 schrieb, gar nicht darum geht, “das Nichtexistente” zu beweisen, sondern Aussagen bezüglich der Nichtexistenz von Objekten mit bestimmten Eigenschaften.)

  28. #28 demolog
    19. August 2017

    @ Tox
    19. August 2017

    Ergo, Ihr Satz

    Das Nichtexistente ist nicht beweisbar …

    ist nicht sinnvoll? (Da es, wie ich in Kommentar #23 schrieb, gar nicht darum geht, “das Nichtexistente” zu beweisen, sondern Aussagen bezüglich der Nichtexistenz von Objekten mit bestimmten Eigenschaften.)

    -> Die Unterscheidung scheint mir sinnvoll. Ob sie unser Problem lösst, weiß ich nicht.
    Es hängt eben davon ab, wie sich das formale System damit abfindet, in dem die Entscheidung zu treffen ist – ob es gar sinnvoll erweitert werden kann.

    Ich bin nun aber auch schon weitergezogen mit meiner Aufmerksamkeit.

  29. #29 Karl-Heinz
    19. August 2017

    Pinocchios Nase wächst bekanntlich genau dann, wenn er lügt. Was passiert aber, wenn er sagt „Meine Nase wächst gerade“?

  30. #30 Tox
    19. August 2017

    @demolog:

    Die Unterscheidung scheint mir sinnvoll.

    Die Unterscheidung ist sicher in gewissem Maße sinnvoll. Ich habe nichts gegenteiliges behauptet; es war ja Erik, der keine Differenz entdecken konnte (vgl. Kommentar #24) und nicht ich. Allerdings ist sie in gewissem Sinne trivial; einen Beweis einer nichtexistenten Aussage kann es offensichtlich nicht geben, und ebensowenig Beweise von Objekten die keine Aussagen sind. Und sie hat wie gesagt nichts mit unserer “Diskussion” zu tun.

    Ob sie unser Problem lösst, weiß ich nicht.

    Und was genau wäre “unser Problem”? Dass Sie eine offensichtlich falsche Behauptung aufstellen, dies aber nicht einsehen wollen?

  31. #31 Laie
    21. August 2017

    @Karl-Heinz
    Pinocchio kann in Wirklichkeit gar nicht sprechen, nichts passiert!

  32. #32 Karl-Heinz
    21. August 2017

    @Laie

    Na gut, dann andersrum.
    „Wenn ich sage, dass ich lüge, lüge ich oder sage ich die Wahrheit?“

  33. #33 Bote17
    21. August 2017

    Thilo,
    nichtdeterministische Turingmaschine, wie ist die zu denken?
    Ein Zufallsgenerator ?
    Ein Sortierverfahren, das nach Versuch und Irrtum arbeitet?
    Nenne mal ein Beispiel!

  34. #34 Karl-Heinz
    21. August 2017

    @Bote17

    Eine NTM unterscheidet sich von einer DTM dadurch, dass der aktuelle Zustand und das aktuelle Bandsymbol diese drei Dinge nicht mehr eindeutig festlegen, vielmehr gibt es mehrere mögliche Übergänge. Die NTM hat also für jede Eingabe nicht etwa einen eindeutigen Lauf, sondern viele verschiedene mögliche Läufe. (Das kann so interpretiert werden, dass sie zufällig einen der möglichen Läufe ausführt, oder aber so, dass sie alle möglichen Läufe parallel ausführt.) Sie akzeptiert die Eingabe, sofern es einen akzeptierenden Lauf gibt.

    Da dieses Verhalten nach heutigem Kenntnisstand nicht ohne Weiteres realisierbar ist, handelt es sich um ein theoretisches Maschinenmodell. Trotzdem hat dieses Modell aus verschiedenen Gründen eine große Bedeutung für die theoretische Informatik, insbesondere für den Bereich der Komplexitätstheorie.

  35. #35 michael
    21. August 2017

    > Nenne mal ein Beispiel

    Ein Beispiel findet man hier

    oder hier.
    .

  36. #36 Thilo
    21. August 2017

    Anschaulich: eine nichtdeterministische Turingmaschine darf versuchen, die richtige Lösung zu erraten – sie muß dann aber die Korrektheit der Lösung mathematisch exakt beweisen. Eine deterministische Turingmaschine hingegen muß die Lösung mit einem vorher festgelegten Akgorithmus finden – nicht nur das Bestätigen sondern auch das Finden der Lösung ist deterministisch.

  37. #37 Bote17
    21. August 2017

    Thilo, Michael, Karl-Heinz
    Danke, so ähnlich habe ich mir das vorgestellt.
    Jetzt mal praktisch. Gibt es Erfahrungen , welcher Algoritmus schneller arbeitet, der der NTM oder der DTM?
    (am gleichen Problem natürlich)

  38. #38 Karl-Heinz
    22. August 2017

    @Bote17

    Jetzt mal praktisch. Gibt es Erfahrungen, welcher Algorithmus schneller arbeitet, der der NTM oder der DTM?
    (am gleichen Problem natürlich)

    Ich weiß jetzt nicht genau was du meinst.
    DTM steht für deterministische Turing-Maschine
    NTM bzw. NDTM steht für nichtdeterministische Turingmaschine

  39. #39 Tox
    22. August 2017

    @Bote17:
    Jede DTM ist auch eine NTM (bzw. genauer: es gibt zu jeder DTM eine NTM die exakt dasselbe tut). Folglich sind NTMs stets mindestens so schnell wie DTMs.

    Ob es Probleme gibt für die NTMs signifikant schneller sind als DTMs ist ja gerade das P=NP Problem.

  40. #40 Bote17
    22. August 2017

    Karl-Heinz,
    ob du es Turingmaschine nennst oder Programm oder Algoritmus, alle tuen das gleiche.
    Tox,
    wenn du einProgramm hättest, der jede Primzahl mit einem vorher festgelegten Algoritmus errechnen könnte, was es bis jetzt nicht gibt, dann wäre das ein DTM.
    Also kann man nur durch Versuch und Irrtum , was der NTM entspricht, die Primzahlen lückenlos finden.
    Deswegen ist Deine Aussage, dass DTMs mindestens genau so schnell sind wie die NTMs, gewagt, weil an diesem Beispiel ein Vergleich nicht möglich ist.
    Deswegen wollte ich doch ein anderes Beispiel, z.B. anhand von Sortierverfahren haben, die diese beiden Verfahrensweisen simulieren.

  41. #41 Tox
    22. August 2017

    @Bote17:
    Selbstverständlich gibt es Algorithmen, die nacheinander alle Primzahlen ausgeben. Und nein, eine NTM ist nicht “Versuch und Irrtum”.
    Ich habe auch nicht gesagt, dass DTMs mindestens genau so schnell sind wie NTMs, sondern dass NTMs mindestens so schnell sind wie DTMs.

  42. #42 Karl-Heinz
    22. August 2017

    ob du es Turingmaschine nennst oder Programm oder Algoritmus, alle tuen das gleiche

    Nö, das stimmt so nicht.
    Auf einer Turing-Maschine kann ich ein Programm ausführen lassen.
    Übrigens Algoritmus schreibt man so Algorithmus

  43. #43 Bote17
    22. August 2017

    Karl-Heinz,
    sachlich gesehen ist es natürlich nicht das Gleiche, sonst gäbe es ja nicht verschiedene Begriffe.
    Es geht doch um die innere Logik.
    Eine software simuliert (erspart) die Hardware.
    Eine Turingmaschine. ein PC z.B. besitzt einen Prozessor, der 1000 verschiedene Aufgaben erfüllen kann. welche er erfüllt , entscheidet die Software, also das Programm, mit dem Algorithmus. Klar jetzt?
    Und hier wird gefragt, ob ein Programm, dass einen vorher festgelegten Ablaufplan hat, schneller ist, als ein Programm, dass verschiedene Verzweigungen ermöglicht und dadurch vielleicht schneller läuft.
    Das könnte man in einem praktischen Vergleich sehen. aber in der Informatik will man ja einen grundsätzlichen Beweis, einen deduktiven Beweis.
    thilo
    habe ich das richtig interpretiert?

  44. #44 Tox
    23. August 2017

    @Karl-Heinz:
    Meines Wissens nach betrachtet man üblicherweise das Programm/den Algorithmus als Teil der Turingmaschine. D.h. man gibt eine passende Zustandsmenge und eine Übergangsfunktion an, die zusammen den Algorithmus darstellen. Das Band enthält dann nur noch die Eingabedaten.
    Selbstverständlich könnte man auch eine “Universal-Turingmaschine” konstruieren, d.h. einen Interpreter der sowohl das Programm als auch die Eingabedaten von Band liest, aber das ist meines Wissens nach nicht die übliche Vorgehensweise.

    @Bote17:
    Nur falls das nicht klar sein sollte: Nichtdeterministische Turingmaschinen sind lediglich theoretische Modelle und keine realen Maschinen. Ein praktischer Vergleich ist daher unmöglich.

    Vielleicht hilft ein Beispiel (als Vorwarnung: es ist schon eine ganze Weile her dass ich mich damit genauer beschäftigt habe; es ist also gut möglich, dass nicht alles ganz korrekt ist): Eines der bekanntesten und anschaulichsten NP-Probleme ist das “Problem des Handlungsreisenden” (traveling salesman). Als Entscheidungsproblem lautet es: Gegeben sei eine Liste von Städten und den paarweisen Entfernungen zwischen diesen sowie eine Maximallänge L. Gibt es eine Rundreise durch alle Städte, deren Gesamtlänge kürzer als L ist?

    Eine nichtdeterministische Maschine könnte dieses Problem folgendermaßen lösen: Falls es eine ausreichend kurze Rundreise gibt, rät die Maschine eine solche. Dann berechnet sie ihre Länge und weist damit nach, dass es tatsächlich eine Rundreise mit der gewünschten Eigenschaft gibt. Falls es keine solche Rundreise gibt, macht die Maschine etwas anderes; bei der Frage ob ein Problem zu NP gehört, ist dieser Fall nicht relevant.

    Wie die Maschine es schafft, im ersten Fall immer richtig zu raten, ist nicht spezifiziert. Wie gesagt, NTMs sind theoretische Modelle und für reale Computer eher nicht relevant.

  45. #45 Bote17
    23. August 2017

    tox,
    ….nichtdeterministische Maschinen,
    jede CPU wird durch ein Programm nichtdeterministisch,
    wenn das Programm das fordert.
    Jede Software kann als simulierte Hardware aufgefasst werden. Das ist doch das Geheimnis der Personalcomputer. Man braucht keinen Taschenrechner mehr, man braucht keinen Synthesizer mehr, man braucht kein Notizbuch mehr, das alles schaft die Software. Die CPU setzt die Befehle der Software so um als ob es genau diesen Computer gäbe. Diese software ist meistens determiniert, d.h. der Programmablauf ist von vornherein festgelegt.
    Was aber, wenn das Programm Knotenpunkte enthält, wo durch Zufall entschieden wird, welchen Weg das Programm nimmt. Wenn sich dann der Weg als richtig heraustellt, dann war die Programmierung nicht determiniert und wenn der Zeitaufwand geringer ist alsbei einem determinierten Programm, dann hätten wir praktisch das Problem gelöst. Aber leider nur praktisch.
    Übrigens: Das Problem des Handlungsreisenden kann man mit analogen Maschinen leicht lösen.
    Wenn ich mich richtig erinnere, sägt man in eine Holzplatte soviele Löcher, wie die Anzahl der Städte, die der Handlungsreisende besuchen soll.Der Abstand der Löcher stellt die entfernungen dar. Dann fädelt man durch die Löcher Seile, an denen Gewichte hängen. Oberhalb der Platte sind die Seile alle zusammengeknotet. Der gemeinsame Knoten stellt dann den Ausgangspunkt des Handlungsreisenden dar. Er ist der optimale Ausgangspunkt, hervorgerufen durch die Zugkräfte der Seile , die aus verschieden Richtungen an diesem Knoten ziehen.
    Jetzt muss ich passen, ich weiß nicht mehr wie dann die Reihenfolge der Orte aus dem Bild auszulesen ist, dass wie ein Spinnennetz aussieht. Aber vielleicht kann sich jemand anderes an diese analoge Lösung erinnern.

  46. #46 Karl-Heinz
    23. August 2017

    Zum Spielen Kürzeste Rundtouren “Problem des Handlungsreisenden”

    https://www-m9.ma.tum.de/games/tsp-game/index_de.html

  47. #47 Karl-Heinz
    23. August 2017

    @Bote17

    Warum für das “Problem des Handlungsreisenden” umständlich Löcher in die Tischplatte bohren?
    Nimm einfach den Schleimpilz Physarum polycephalum.

    https://www.spektrum.de/news/virtuelle-denkmasse-loest-problem-des-handlungsreisenden/1189677

  48. #48 Karl-Heinz
    23. August 2017

    Ein sehr guter Artikel zum NP Problem

    https://www.sueddeutsche.de/wissen/mathematik-problem-not-eines-handlungsreisenden-1.588630

  49. #49 Tox
    23. August 2017

    @Bote17:

    jede CPU wird durch ein Programm nichtdeterministisch,
    wenn das Programm das fordert.

    Nein. Solange es von außen keine nichtdeterministische Eingabe gibt (und die CPU nicht defekt ist), verhalten sich CPUs streng deterministisch.

    Jede Software kann als simulierte Hardware aufgefasst werden.

    Ja, und? Habe ich je etwas anderes behauptet?

    Was aber, wenn das Programm Knotenpunkte enthält, wo durch Zufall entschieden wird, welchen Weg das Programm nimmt. Wenn sich dann der Weg als richtig heraustellt, dann war die Programmierung nicht determiniert und wenn der Zeitaufwand geringer ist alsbei einem determinierten Programm, dann hätten wir praktisch das Problem gelöst. Aber leider nur praktisch.

    Zunächst einmal ist wie gesagt “echter” Nichtdeterminismus in derzeit existenten Computern nur durch Input von außen möglich. Und nein, das Problem ist dann auch nicht praktisch gelöst. Wenn Sie kein Vorwissen darüber haben, welcher Weg vermutlich der bessere ist, wird eine zufällige Entscheidung im Mittel zu einer längeren Laufzeit führen. Und wenn hingegen ein solches Wissen vorliegt, dürfte ein streng deterministisches Vorgehen der Art “wähle zunächst den vermutlich besten Weg, und wenn sich dieser als falsch herausstellt, dann wähle den nächstbesten etc.” besser sein als eine Zufallsentscheidung.

    Übrigens: Das Problem des Handlungsreisenden kann man mit analogen Maschinen leicht lösen.

    Ja, und? Ich habe nicht nach einer Lösung dieses Problems gefragt, sondern es als ein Beispiel verwendet um die Problemklasse NP zu beschreiben.

  50. #50 Bote17
    23. August 2017

    tox,
    ……Wenn Sie kein Vorwissen darüber haben, welcher Weg vermutlich der bessere ist, wird eine zufällige Entscheidung im Mittel zu einer längeren Laufzeit führen. Und wenn hingegen ein solches Wissen vorliegt, dürfte ein streng deterministisches Vorgehen der Art “wähle zunächst den vermutlich besten Weg, und wenn sich dieser als falsch herausstellt, dann wähle den nächstbesten etc.” besser sein als eine Zufallsentscheidung.”
    Damit haben Sie den Kern des Problems sehr gut beschrieben.
    Die Annahme, dass zufällige Entscheidungen mehr Zeit brauchen, bleibt eine Annahme.

    Jetzt mal zur Theorie,
    streng nichtdeterministisch gibt es in der Praxis nicht. Da haben Sie Recht. Selbst ein Zufallsgenerator ist letzlich deterministisch.
    Ich habe ja auch nur versucht einen Ausgangspunkt zu finden, wie man das Problem anpacken sollte.
    Mein Beispiel mit den analogen Lösungen diente auch nicht dazu vom Thema abzulenken, sondern den Gesichtskreis zu erweitern. Ich denke jetzt mal spontan an eine stochastische Lösung. Vielleicht hilft das weiter.

  51. #51 Laie
    24. August 2017

    @Tox
    Wenn in einem Computer der Lüfter defekt wird und überhitzt oder der Blitz im Baum nebenan einschlägt, dann verhält sich die CPU nicht deterministisch.

    In modernen Computern gibt es eine Reihe *weiterer Quellen, die zu Nichtdeterminismus führen.

    *[Früher war das anders]

  52. #52 Tox
    24. August 2017

    @Bote17:

    Die Annahme, dass zufällige Entscheidungen mehr Zeit brauchen, bleibt eine Annahme.

    Da die “Problemstellung” so vage ist, lässt sich das kaum vermeiden. Ich halte es jedoch für sehr plausibel; es wird höchstwahrscheinlich Wege durch das Programm geben, die erst nach sehr langer Zeit terminieren, oder gar zu Endlosschleifen führen, also zu einer unendlichen Programmlaufzeit. Solange auch solche Wege mit nichtverschwindender Wahrscheinlichkeit gewählt werden, wird der Erwartungswert der Laufzeit sehr hoch werden.

    Ich habe ja auch nur versucht einen Ausgangspunkt zu finden, wie man das Problem anpacken sollte.

    Welches Problem?

    Vielleicht hilft das weiter.

    Nein, tut es nicht. Nocheinmal: Ich habe das Problem des Handlungsreisenden nur erwähnt, um Ihnen ein Beispiel für ein Problem der Klasse NP zu geben. Nicht, um dieses Problem an sich zu diskutieren oder “alternative” Lösungen zu finden.
    Vielleicht wäre ein weniger anschauliches Beispiel besser geeignet gewesen.

    @Laie:
    Siehe mein Kommentar #49

    Solange es von außen keine nichtdeterministische Eingabe gibt (und die CPU nicht defekt ist), …

  53. #53 rexlip
    24. August 2017

    tox,
    ist N = NP
    ein sprachliches Problem, philosophisches Problem,
    was ist der Sinn dieser Klärung?

  54. #54 Tox
    24. August 2017

    @rexlip:
    P=NP ist ein mathematisches Problem, bzw. genauer eines der theoretischen Informatik (vgl den ersten Satz des Artikels oben).

    was ist der Sinn dieser Klärung?

    Welcher Klärung?

  55. #55 rexlip
    24. August 2017

    tox,
    wir sprechen nicht die gleiche Sprache. Ciao!

  56. #56 erik||e oder wie auch immer . . . ..
    24. August 2017

    @Tox
    . . . .. P=NP ist ein Anwendungsproblem, ein Entscheidungsproblem
    . . . .. ähnlich wie der Markov-chain-generator . . . ..
    . . . .. bei Markov: sichere Entscheidungen zu treffen
    . . . .. bei P=NP: Wie sicher sind meine Entscheidungen?

  58. #58 michael
    2. September 2017

    The proof is wrong.

  60. #60 Laie
    6. September 2017

    Warum hat man hier alles auf kursiv umgestellt?
    Fehlt irgendwo ein schliessender – Tag oder schliessender -Tag?

  61. #61 Thilo
    6. September 2017

    Der Nachtrag vom 2.9. hatte eine fehlerhafte Formatierung. Ist jetzt korrigiert.