Lösung des P-NP-Problems?


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

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


    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. Mir war nicht bekannt, dass jemand einen solchen Beweis erbracht hätte - ich habe ihn jedenfalls gestern erbracht.

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

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


    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.

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

  • 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

  • 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


    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.

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

    Better to reign in hell,
    than serve in heaven.
    (John Milton, Paradise Lost)

  • ewigwährenden Ru(h)m


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


    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?

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


    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.

    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.


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

    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

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


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

    Better to reign in hell,
    than serve in heaven.
    (John Milton, Paradise Lost)

  • Gut, dass du etwas konkreter geworden bist. Mit manchen Einwänden hast du Recht, aber zu einigen möchte ich noch etwas anmerken.

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


    Aber eine sehr elegante Möglichkeit. Ich zitiere aus Wikipedia: "NP (nichtdeterministisch polynomielle Zeit) ist in der Informatik eine Komplexitätsklasse aus dem Bereich der Komplexitätstheorie. Sie bezeichnet die Klasse aller Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine bezüglich der Eingabelänge in Polynomialzeit entschieden werden können."

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


    Verwechselst du da nicht Berechenbarkeit und Komplexität? Wir haben in der Vorlesung "Advanced Topics in Theoretical Computer Science" gelernt, dass jede Turingmaschine in der Lage ist, eine semientscheidbare Sprache zu verarbeiten, so dass sie "ja" zurückgibt, wenn ein Wort in dieser Sprache enthalten ist, und entweder "nein" zurückgibt oder in eine Endlosschleife gerät, wenn nicht. Ob das in polynomieller oder exponentieller Zeit geschieht, ist eine Frage der Komplexität und für die Frage der Berechenbarkeit nicht relevant.

    Wikipedia schreibt: "Systeme, Computer und Programmiersprachen, die unter Ausblendung der Beschränktheit des Speichers und damit verbundenen Eigenschaften eine Turingmaschine emulieren könnten, werden als turingvollständig bezeichnet." Sowie: "Obwohl solche Maschinen physikalisch unmöglich sind, da sie unbegrenzten Speicherplatz besitzen müssten, wird der Begriff Turing-vollständig bei gängigen Programmiersprachen und Computern angewandt, die universell wären, wenn sie unbegrenzten Speicher besäßen. Charles Babbages Analytical Engine wäre in diesem Sinne Turing-vollständig gewesen, wenn sie jemals gebaut worden wäre. Die erste Maschine, von der die Turing-Vollständigkeit sicher bekannt ist, die programmgesteuerte Z3 von Konrad Zuse, wurde 1941 gebaut. Die Universalität dieses Rechners war jedoch in der Zeit seiner Entstehung noch unbekannt und wurde erst später bewiesen. Alle modernen Computer sind ebenfalls im weiteren Sinne Turing-vollständig."

    Formale Definition ist das aber keine und daneben auch ungenau. Um die Definition etwas zu formalisieren:


    OK, danke.

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


    OK, das habe ich ungenau formuliert.

    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.


    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.

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


    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.

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

    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.

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

    Better to reign in hell,
    than serve in heaven.
    (John Milton, Paradise Lost)

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


    OK, jetzt hast du verstanden, wie der Satz gemeint war.

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


    Im Moment wüsste ich noch nicht, wie man einen solchen Beweis führen könnte. Es ist leicht zu zeigen, dass es einen Algorithmus gibt, wenn man ihn kennt, aber schwierig zu zeigen, dass es keinen Algorithmus geben kann.

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


    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.

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

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

    Better to reign in hell,
    than serve in heaven.
    (John Milton, Paradise Lost)

  • Ich meine damit, dass es Probleme gibt, für die es eine exponentielle Anzahl an Lösungskandidaten gibt, man aber nur eine polynomielle Anzahl von Lösungskandidaten untersuchen muss, weil man die übrigen Lösungskandidaten von vornherein ausschließen kann.

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!