Traveling-Salesman-Problem gelöst?

[DarkDragon]

Hallo,

Glaubt ihr daran, dass das Salesman-Problem schonmal gelöst wurde und der Lösungsweg* eventuell vom Militär oder sonstigen Geheimhaltungs-Organisationen schon zu geheimen Zwecken genutzt wird?

http://de.wikipedia.org/wiki/Problem_de ... sreisenden

* Hierunter versteht sich für mich die Umwandlung einer Exponentialfunktion [Bruteforce] in eine ganzrationale Funktion [Einfache Schleife] (für mich unmöglich, es soll aber Leute geben, die es geschafft haben Gerüchten zufolge...)

Hier z.B. soll es jemand gelöst oder teilweise gelöst haben:
http://www.sciencedaily.com/releases/20 ... 075125.htm

[hardfalcon]

So eine Frage ließe sich viel einfacher beantworten, wenn man die vollständigen Budgets der 10 größten Geheimdienste der Welt sowie der 50 größten zivilen Rechenzentren vorliegen hätte...

[DarkDragon]

So eine Frage ließe sich viel einfacher beantworten, wenn man die vollständigen Budgets der 10 größten Geheimdienste der Welt sowie der 50 größten zivilen Rechenzentren vorliegen hätte...

Selbst das NASA Rechner Verbindungs Programm zu einem Uber-Rechner würde das TSP nicht so einfach Lösen.

[hardfalcon]

Dann gilt der Grundsatz, dass Militär und Geheimdienste ein parasitärer Befall der Forschung sind...

[Franky]

Es fehlt die Antwortmöglichkeit "Ja, von mir"

[Froggerprogger]

Die Antwort ist ganz klar ja, denn ich kann das TSP auch lösen. Das ist gar keine Kunst. Schwierig wird es, das TSP in polynomieller Zeit zu lösen.

Leider ist das äquivalent dazu, dass NP=P, aber nahezu sämtliche Wissenschaftler gehen von NP<>P aus, und auch nach nur wenig Beschäftigung damit legt die Intuition einem NP<>P nahe, es hat bloß noch keiner beweisen können. Das ist DAS Problem der Komplexitätstheorie und könnte im Falle NP=P heftigste Auswirkungen haben. Hier ein Link zum Thema: http://de.wikipedia.org/wiki/P/NP-Problem

Daher vermute ich mal nein.

[Karl]

Basieren die Komplexitätsklassen nicht auf Turingmaschinen? Würde eine andere Basis eine Lösung in polynomineller Zeit zulassen. TM sind an sich ja Schritt-für-Schritt-Maschinen. Vielleicht haben sie eine echte Parallelmaschine gefunden, die das kann. Mit Quantencomputern soll ja einiges möglich sein.

Gruß Karl

[Froggerprogger]

Turingmaschinen und Registermaschinen (also insbesondere jeder Von-Neumann-Rechner, also im Prinzip jeder PC) führen zumindest für NP und P zu denselben Komplexitätsklassen, denn die Bauweisen lassen sich gegenseitig mit nur polynomieller Zeitänderung aufeinander simulieren.
Da helfen auch keine Multiprozessorregistermaschinen, denn die können eine Registermaschine höchstens um einen konstanten Faktor beschleunigen.

Quantencomputer sind etwas ganz anderes, für die greifen die Aussagen über Turingmaschinen nicht. Die verschränkten QuBits nehmen einfach alle entsprechenden Lösungszustände an, womit man z.B. riesige Zahlen superschnell faktorisieren könnte. Eines der größten Probleme dabei ist wohl, viele der QuBits miteinander zu verschränken, so ist dies wohl für 8 schon gelungen (ein QuByte), aber noch lange nicht für 32 oder gar 64, denn das Problem skaliert schlecht, wird also überproportional schwerer für zunehmende Größe. Details weiß ich da aber nicht drüber, freue mich aber schon auf die Vorlesung 'Quantencomputer' im übernächsten Semester.