P=np?

[Lorenzy]

Zitat von richy

Doch, das geht mit neronalen Netzwerken. Ein Kohonen Netztwerk loest das Problem des Handlungsreisenden innerhalb weniger Minuten.

Hi richy,

Mit diesem Trick kann auch "nur" eine Annährung des Problems des Handlungsreisenden erreicht werden. Es gibt aber nur eine Lösung - die kürzeste Strecke. Selbst wenn man mit solchen neuronalen Netzwerken den Weg durch 50 Städte berechnen würde, hätte man immer noch Millionen von möglichen Lösungen, welche aber alle (zufällig könnte sich natürlich auch der heilige Gral darunter befinden) nur Annährungen des Problems sind.
Das soll natürlich nicht die Leistung solcher neuronalen Netzwerke schmälern. Es ist schon erstaundlich was in so kurzer Zeit damit erreicht werden kann - Annährung hin oder her.

Die derzeit einzigen Kandidaten um NP-Probleme in zumutbarer Zeit zu lösen, sind Quantenrechner bzw. deren Algorithmen.

[Marco Polo]

Zitat von richy

Doch, das geht mit neronalen Netzwerken. Ein Kohonen Netztwerk loest das Problem des Handlungsreisenden innerhalb weniger Minuten.
Das Netzwerk ist so einfach, dass man es leicht selber Programmieren kann.

Hi richy,

Kohonen Netzwerk? Klingt interessant. Hast du da mehr Infos zu?
Ich denke aber, dass das Problem des Handlungsreisenden kein NP- vollständiges Problem ist, sondern lediglich ein NP Problem.

Wenn du z.B. 20.000 Knotenpunkte hast, dann soll das ein leicht zu programmierendes Netzwerk in so kurzer Zeit lösen können? Ich bin da eher skeptisch. Braucht man dafür nicht eher Grossrechner?

Gruss, Marco Polo

[Gandalf]

Hi!

Ich denke aber, dass das Problem des Handlungsreisenden kein NP- vollständiges Problem ist, sondern lediglich ein NP Problem.

Möglicherweise ist es nur ein P-Problem. Meines Wissen gibt es hier in der Mathematik unterschiedliche Auffassungen. Einmal hier: http://lexikon.meyers.de/meyers/Spez...easerID=100340, wonach das "Problem des Handlungsreisenden" als NP-Problem dargestellt wird, - andererseits finde ich plausibler, dass dies nur ein 'P-Problem' ist, da es in 'vernünftiger Zeit' proportional zu n-Rechenschritten offenbar zu lösen ist, wie richy bereits erwähnt hat. Primzahlfaktorisierungen würden hier demgegenüber wahre NP-Probleme darstellen, da die erforderlichen Rechenschritte hier exponentiell zunehmen.

Ein 'NP-Vollständiges Problem' wäre demnach ein Algorithmus der das Faktorisierungsproblem löst. Und so einer ist nicht bekannt.

[Lorenzy]

Zitat von Gandalf

Möglicherweise ist es nur ein P-Problem.

Hi Gandalf,

Möglich. Aber Spekulationen sind bei solchen Problemen fehl am Platze. Die Knacknuss ist ja, es zu beweisen bzw. zu widerlegen. Raten kann jeder.

andererseits finde ich plausibler, dass dies nur ein 'P-Problem' ist, da es in 'vernünftiger Zeit' proportional zu n-Rechenschritten offenbar zu lösen ist, wie richy bereits erwähnt hat.

Eine Annäherung ist noch keine Lösung.

[wusel]

Hallo Lorenzy,

Intermezzo

Eine Annäherung ist noch keine Lösung.

Tailorreihe, Regulafalsi oder Newtonverfahren ... sind (Lösungen der Numerik), ja sicherlich Nährungen ... aber ohne die, hätte ich zu meiner Schulzeit nicht mal ein Tafelwerk besessen. Kennst Du noch einen Rechenstab? Zu meiner Zeit "Schätzeisen" genannt? Ob Taschenrechner, PDA oder Klapprechner ... wo man hin sieht, Polynome ...

Kosmologie interessiert mich eigentlich sehr, aber irgenwie habe ich auf dem falschem Bahnsteig gestanden (bzw. ich war lange nicht vor Ort) ... Der Zug scheint weg.

[Lorenzy]

Zitat von wusel

Tailorreihe, Regulafalsi oder Newtonverfahren ... sind (Lösungen der Numerik), ja sicherlich Nährungen ... aber ohne die, hätte ich zu meiner Schulzeit nicht mal ein Tafelwerk besessen. Kennst Du noch einen Rechenstab? Zu meiner Zeit "Schätzeisen" genannt? Ob Taschenrechner, PDA oder Klapprechner ... wo man hin sieht, Polynome ...

Hi Wusel,

Ich wolllte damit ausdrücken, dass man dem Problem N=NP? mit einer Annährung auch nicht näher kommt.

[Marco Polo]

Zitat von Lorenzy

Ja. Ziemlich OT hier. Die Lösung hierzu heisst MP.

Du sagst es Lorenzy.


Obige Beiträge wurden auf Anregung von Lorenzy hierhin verschoben.

Ausser den Beitrag von richy. Den habe ich kopiert, da er nicht OFF-Topic war,
aber dennoch teilweise hier reinpasst.

[Lorenzy]

Hi Marco Polo,

Das ging ja schnell. War wohl kein NP-Problem.

[Marco Polo]

Zitat von Lorenzy

Hi Marco Polo,

Das ging ja schnell. War wohl kein NP-Problem.

Doch, es war ein NP-Problem.

Ich habe aber schnell ein Kohonen-Netzwerk programmiert.

Gruss, Marco Polo

[Marco Polo]

In der JULI-Ausgabe der Spektrum der Wissenschaft, gibt es einen Bericht "Grenzen der Quantencomputer", der sich auch mit P und NP Problemen beschäftigt. Vielleicht stelle ich am Donnerstag eine kurze Zusammenfassung hier rein. Vorher komme ich leider nicht dazu.

Gruss, Marco Polo