Ich habe gelesen, daß das P/NP-Problem eines der ungelösten Probleme der Mathematik ist.
Schon beim Durchlesen der Beschreibung habe ich mir gedacht:Das ist doch genau das Problem das beim Routing in Netzwerken auftritt.
Dann hab ich mir auf Wikipedia den Eintrag zum Routing und dann den Eintrag zum "Dijkstra-Algorithmus" gelesen.
Hier wird haargenau die Lösung zum Problem des Handelsreisenden erklärt, was aber eigentlich laut ungelöstem P/NP-Problem in der Mathematik mit der Anzahl der vorhanden Knoten im Internet niemals möglich sein sollte weil das Ausrechnen der besten Route fast unendlich lange dauern sollte. (so 500 Milliarden Jahre bei 64 Knoten).
Wie ist es also möglich von einem ungelöstem Problem zu sprechen wenn doch das gesamte Internet auf diesem Problem und seiner Lösung aufgebaut ist?
.
Best answer:
Answer by Ford Prefect
Hmm ich denke du hast da was missverstanden. Das Problem das Handelsreisenden ist ein Beispiel für ein Problem aus der Komplexitätsklasse NP, und der Bezug zum P-NP-Problem ist nur insofern gegeben, dass es in dem Fall P=NP bewiesen wäre, dass es einen effizienten Algorithmus gibt, um das Problem zu lösen.
Das Problem selbst beschreibt die Schwierigkeit des Handelsreisenden, eine optimale Route zu finden, mit der er ALLE Städte bereist. Beim Routing ist das Problem viel einfacher: Man sucht nur den kürzesten Weg von einem Zielknoten zu einem Endknoten, egal, über welche Zwischenknoten er geht.
Im Gegensatz zum Problem des Handelsreisenden ist das Routing-Problem nicht NP-vollständig, und deshalb existiert auch ein effizienter Algorithmus dafür.
Um zu P-PN zurückzukommen: Dieses ungelöste Problem bezieht sich auf die Frage, ob Probleme, die von nichtdeterministischen Turingmaschinen in Polynomialzeit gelöst werden können, immer auch von deterministischen Turingmaschinen in Polynomialzeit lösbar sind.
(Um ein Beispiel zu nennen: Im Falle von P=NP wäre bewiesen, dass es für jedes Verschlüsselungssystem einen effizienteren Entschlüsselungsalgorithmus gibt als Bruteforcing)
Selbst wenn P=NP wäre, wäre die Existenz eines effizienten Algorithmus für NP-vollständige Probleme nur bewiesen, aber sie lassen sich daraus noch lange nicht herleiten. Auf die Praxis bezogen hätte diese Feststellung also nicht ganz so schwerwiegende Folgen, wie manchmal behauptet wird. Denn was nützt es, zu wissen, dass es einen effizienten Algorithmus für die Lösung eines Problems gibt, wenn man ihn nicht kennt?
What do you think? Answer below!
Also P und NP sind Aufwandsklassen. Zu der Klasse P gehören alle Algorithmen, die in "polynomieller" Zeit gelöst werden können. NP bedeutet, sie sind in "nicht polynomieller" Zeit lösbar. Das unlösbare Problem ist nun, sind beide Aufwandsklassen gleich. Das hätte zur Folge, daß ein Problem, welches in NP liegt (und damit schwer/langsam zu lösen ist) so umgeschrieben werden kann, daß es in P liegt (und damit relativ leicht/schnell zu lösen ist). Bezogen auf dem Dijkstra-Algorithmus würde das bedeuten, das Problem wäre auf dem gleichen Rechner nicht in 500 Milliarden Jahren, sondern vielleicht schon nach 100 Milliarden Jahren gelöst.
AntwortenLöschenBeim routing geht es nicht um den kürzesten Weg, sondern um den Ansatz eines möglichen weges.
AntwortenLöschenIp-Adressen sind Lokal gebunden. wenn alle Pakete, die nach der Analyse der Ip in die USA müssen, zum Beispiel nach New-York geroutet werden, dann sind die Daten dort richtig. Wenn der Router in New-york alle Adressen, die im Staat Colorado liegen, nach colorado Springs routet, dann sind die Daten in colorado springs auch erst mal richtig. Wenn´in colorado springs die Daten für Aspen dann nach Aspen geroutet werden, dann passt das auch. Aber der Router in Frankfurt muss nicht wissen, daß die Daten für Aspen in Colorado springs umgeroutet werden, der muss nur wissen, daten in die USA nach new York.
Es geht beim routing also nicht um den kürzesten Weg, sondern um den Ansatz eines möglichen Weges.