Traveling salesman und andere gelösst?

Wissenschaft Informatik
#1

Hallo Experten,

habe mich versucht etwas mit der Veröffentlichung von Plotnikov auseinanderzusetzen. Unten findet Ihr einen Link zu dieser.
(in postscript und gnu-gezipt…)

http://www.geocities.com/st_busygin/clipat.html

Mal abgesehen davon, dass ich dem nicht folgen kann, gibt es hier jemand, der diesem durchaus Glauben schenken könnte und warum? Was würde der Beweis dieser These für Folgen haben?

Ich bin mal ganz schnell darauf gekommen:

super-schnelle Suchalgorithmen
Datenbanken unvorstellbarer Größe…

Freue mich auf eine rege Diskussion

MfG Dennis

#2

…

http://www.geocities.com/st_busygin/clipat.html

hab grad gesehen, dass sieben Artikel weiter unten jenes Thema kurz aufgegriffen wurde, lasse meinen Artikel aber wegen dem Link und meiner Fragen…

MfG Dennis

#3

Hi,

wie sich inzwischen herausgestellt hat, ist Plotnikovs Beweis falsch.
Die Konsequenzen, wenn das ganze geklappt haette, waren u.a. voelliger zusammenbruch von ECommerce,Digitaler Signatur etc. gewesen.
Aber auch tolle Loeseungen fuer grosse TSPS :smile:.

MFG
Martin

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

Hi Martin,

wie sich inzwischen herausgestellt hat, ist Plotnikovs Beweis
falsch.

Gibt es Veröffentlichungen im Netz, über die Gegendarstellung??
Woher hast Du die Aussage??

MfG Dennis

#5

Hi Dennis :smile:

Solche Meldungen, dass NP=P ist, sind mit äußerster Vorsicht zu genießen. Horden von Mathematikern und Informatikern haben sich schon daran versucht, ein NP-Problem in polynomialer Laufzeit zu lösen. Alle haben sie keine Lösung gefunden. Immer wieder müssen sie feststellen, dass NPP gilt. Wir müssen, glaube ich, einfach akzeptieren, dass es einige Optimierungsprobleme gibt, die man nur lösen kann, indem man alle Lösungen probiert und dabei die beste heraussucht :smile:))

cu Stefan.

#6

Woher hast Du die Aussage??

MfG Dennis

http://www.geocities.com/st_busygin/clipat.html