Servus Freunde,
es ist ein weiterer Spinner (?!) aufgetaucht, der behauptet, P = NP bewiesen zu haben.
Frage: ist dieser Algorithmus korrekt:
http://rxiv.org/pdf/1212.0109v1.pdf
Der Typ macht etwas, dass er überlagern oder Resolution oder so nennt.
Es ist ja so:
am Montag beweist einer P != NP,
am Mittwoch beweist jemand P = NP,
am Freitag beweist jemand, dass das P-NP-Problem unentscheidbar ist 
so geht das seit Jahrzehnten.
Gruß,
Rainer
Hi,
ist der von Dir?
Keine verlässlichen Quellen, Wikipedia schön und gut, aber es gibt Standardwerke zur Komplexitätstheorie.
Keine Einordnung in die bisherige Geschichte (wer kam nahe, welche ähnlichen Ansätze wurden verfolgt,…).
Alles in allem scheint es zu kurz. Wie sieht es mit Beispielen mit 100 oder 1000 Variablen aus, wie verhält sich die Laufzeit der Implementierung?
Gruß, Lutz
Danke für deine Antwort.
Der Algorithmus ist von einem ‚Louis Coder‘.
Mich interessiert vor allem, ob der Algorithmus korrekt ist.
Jemand eine Idee?
Hochgradig dubious
Hallo,
was mir beim Durchlesen aufgefallen ist:
Im Paper wird von einer maximalen Anzahl von Klauseln gesprochen, die, wenn sie überschritten wird, immer dazu führt, dass das Problem lösbar ist. Ich habe aber nichts dazu gefunden, wie diese maximale Anzahl berechnet wird, und warum diese Anzahl dazu führen soll, dass das Problem lösbar ist. Das ist schon mal „red flag“.
Dann gibt es noch eine Definition von „complexity“, die von der üblichen (Anzahl ausgeführter Rechenschritte) nicht übereinstimmt. Darin sind Kosten zum Suchen und vergleichen der Klauseln nicht mit drin.
Und dann fällt mir auf, dass der Autor behauptet, zwei Jahre lang an diesem Problem getüftelt zu haben, und dann so ein schlecht geschriebenes und unvollständiges Paper ohne stichfeste Referenzen hinrotzt.
Keiner dieser Punkte bedeutet das engültige Aus für diesen Ansatz, aber in einem Feld, in dem so viel Unfug geschrieben wird, reicht es für mich aus, ihn zu begraben, bis ein ordentliches Paper zu einem peer-reviewed Journal eingesandt wird.
Grüße,
Moritz