Sind NP-Probleme, Probleme die nie gelöst werden oder einfach Probleme die mehr als die polynomiale Zeit ihrere Entsprechenden Komplexität zur Lösung brauchen?
Bitte mit Links
4 Antworten
Der Name NP sagts ja schon, die Lösung ist nicht in Polytime in der Eingabegröße findbar. (Wie WP korrekt anmerkte, bedeute NP nondeterministic polytime - mein Fehler - Bliebe noch zu erwähnen, daß wir NTMs nicht realisieren können und eine DTM eine NTM in EXPTIME simulieren kann, wenn diese in POLYTIME löst)
Kleine Problemgrößen sind dabei oft leicht lösbar, bei großen Problemgrößen ist die Lösung nicht in rationaler Zeit findbar.
n=10 n=100 n=1000
n^3: 1 000 1 000 000 1 000 000 000
n^9: 1*10^9 1*10^18 1*10^27
2^n: 1 024 1.2*10^30 1*10^301
n!: 3.6*10^6 9.3*10^157 4*10^2567
Du kannst Dir ja mal überlegen, was 10^2567 Rechenschritte bedeutet, wenn Du 10 TFlops (10^13 Operationen je Sekunde) zur Verfügung hast.
Du hast natürlich recht, daß es nondeterministic polytime ist.
NP Probleme sind welche, bei denen man eine richtige Lösung in polinomialer Zeit prüfen kann. Mit einer nichtdeterministischen Turingmaschine kann man so zusagen alle Fälle gleichzeitig gehen und die Maschine sucht sich den besten raus. Das ist ungefähr äquivalent dazu, eine richtige Lösung zu raten. Danach muss man nur noch prüfen, ob sie die richtige Lösung ist. Und das kann man in polinomialer Zeit.
D.h. Diese Probleme sind lösbar, aber bisher hat man noch nichts gefunden, was mit einer deterministischen Turingmaschine die Lösung in polinomialer Zeit findet.
Das heißt, die Probleme sind so halb lösbar, da sie schnell so groß werden, dass ein Rechner für die Lösung das ganze Universum umfassen müsste.
NP Probleme sind diskrete Probleme. Jedes diskrete Problem ist durch Ausprobieren lösbar, wenn genug Zeit und genug Speicherplatz vorhanden ist.
Und wenn das so einfach stimmt wieso haben sie dies dann nicht mathematisch bewiesen und publiziert und die 1 Millionen Dollar einkassiert?
Ich finde, bei nichtpolynomialen Problemen ist das etwas problematisch, da man in die Region kommen kann, wo das Zerstrahlen eines Sternes von einer Solarmasse nicht ausreicht, um das Problem zu lösen. Das ist dann zwar theoretisch, aber nicht praktisch lösbar.
Die Beschäftigung mit NP Problemen ist ein Problem der theoretischen Informatik. Daher reicht es hier zu zeigen dass es eine theoretische Lösbarkeit gibt.
Die Lösungstheorie von NP Problemen bleibt zunächst ein Problem der theoretischen Informatik. Insbesondere ist das Problem P = NP ein Problem der theoretischen Informatik. Dass es einen Haufen praktischer Probleme lösen würde ist davon unbenommen.
http://www.rither.de/a/witze/mathematikerwitze/feuer-im-hotel/
Nebenbei reicht dem Mathematiker ein Blick auf den Feuerlöscher um wieder zufrieden schlafen zu gehen. Einen Taschenrechner benötigt er selbstverständlich nicht. Der "Witz" ist daher mathematikerfeindlich.
Ich weiß jetzt nicht, ob der Fragensteller in diese Subtilitäten einsteigen will. Ich denke es ist schon relevant zu wissen, dass ein theoretischer Informatiker das noch lösbar nennt, selbst wenn praktisch das ganze Universum in Energie umgesetzt werden müsste, um das Problem genau zu lösen.
Ebenso ist eine Lösung “nichtdeterministisch” wenn sie nicht sicher eine Lösung findet. Das ist auch so, wenn die Lösung nur in einer aus 10 Billionen Fällen zufällig falsch ist. Das ist zwar theoretisch interessant, aber wird in vielen Fällen nicht schlechter sein als die Zuverlässigkeit der Rechenmaschine beim Abfahren eines deterministischen Algorithmus.
Eine "Lösung" ist zunächst mal eine algorithmische Beschreibung des Lösungsvorgangs. Ob dieser konkret anwendbar ist ist dabei nicht die Frage. Eine "nichtdeterministische" Lösung mag praktisch gut anwendbar sein, aber sie ist keine Lösung im eigentlichen Sinn. Wenn der Fragesteller diese "Subtilitäten" nicht verstehen kann, dann verstehe ich den Sinn der Frage nicht.
Man könnte wenige theoretisch lösen - müsste dafür aber jede mögliche Lösung ausprobieren, da es keine Algorithmen zum lösen gibt. Das bedeutet, dass manche "relativ" schnell, andere aber nie gelöst werden könnten.
Ja, auch wenn man vielleicht mal ein System dahinter finden könnte, momentan unlösbar.
Also kann man sagen das sie ohne Algorithmus in endlicher Zeit nie gelöst werden können?
Ja. Aber die Chance ist nicht 0%, eines aus Glück zu lösen, wenn du das noch erwähnen möchtest, wofür auch immer du es brauchst 👍
Du kannst halt keine endliche Zeit zum lösen dieses Problems definieren wenn kein Algorithmus zum lösen dieses Problems bekannt ist
was für diskutieren wir haben uns geeinigt kannst du nicht lesen?
Ich kann lesen. Du behauptest es gäbe NP Probleme die nicht lösbar wären, ich behaupte das Gegenteil. Jedes diskrete Problem ist lösbar. Es benötigt eventuell sehr viel Zeit und sehr viel Speicherplatz, aber das ändert nichts an der theoretischen Lösbarkeit.
Falsch. "Lösbar" meint nun mal theoretische Lösbarkeit, und jedes diskrete Problem ist theoretisch lösbar.
Aus einem anderen Kommentar von mir
Es ist leicht mathematisch zu beweisen dass sich jedes NP Problem algorithmisch lösen läßt. Das Problem ist der Bewies dass NP = P oder NP <> P, also dass sich NP Probleme eben mitpolynomischer Komplexität lösen lassen oder halt nicht.
Es tut mir leid, aber du hast schlicht keine Ahnung von diesem Thema.
da es keine Algorithmen zum lösen gibt
Selbstverfreilich gibt es Algorithmen um NP Probleme zu lösen. Wie kommst du auf dieses schmale Brett? Jedes diskrete Problem läßt sich durch ausprobieren lösen, es dauert halt ein wenig.
Nein, das ist falsch NP heißt, dass es mit einer nichtdeterministischen Turingmaschine in polyminomialer Zeit lösbar ist.