Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
P, NP & Co. als Komplexitätsklassen // deutsch
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 45 Zeilen
- gestern haben wir uns mit algorithmen beschäftigt die eine nicht polygonale laufzeit komplexität haben und wir kamen dazu am ende dass wir gesagt haben
- diese algorithmen generell egal ob sie jetzt polonia oder nicht polonia laufzeit haben die lassen sich in kategorien oder in klassen einteilen und
- genau um diese klassen die sogenannten komplexität klassen geht es heute da gibt es erstmal zwei wichtige die erste komplexität klasse heißt p das ist
- nämlich die klasse aller probleme oder algorithmen die eine polymere laufzeit haben das heißt man könnte sagen die komplexität klasse p enthält alle guten
- probleme alle einfach lösbaren problem all jene probleme für die ein guter algorithmus existiert dafür also ein algorithmus der dieses problem in
- überschaubarer vertretbarer zeit löst die zweite komplexität klasse die sozusagen das gegenstück zu p darstellt die heißt mp das legt nahe dass es für
- nicht poly nominal lösbar steht das ist aber nicht der fall das ist eine kleine stolperfalle in der theoretischen informatik dieses n p steht für nicht
- deterministisch kolonial das bedeutet dass die lösung oder dass ein algorithmus eben nicht in poley nominal zeit das ganze berechnen kann
- aber dass man eine geratene lösung zumindest alter daher geraten deswegen nicht deterministisch dass man eine solche geratene lösung in poley
- nominaler zeit wenigstens überprüfen kann ob es sich denn um eine lösung handelt jetzt ist das besondere an dieser klasse npd dass nicht alle
- probleme die nnp liegen wiederum gleich schwer sind es gibt dort unterschiedliche schwierigkeitsstufen sozusagen
- es gibt zum einen besonders schwierige probleme und es gibt sozusagen noch schwierigere probleme nämlich die die gar nicht lösbar sind auch die sind
- natürlich nicht in poley nominal zeit lösbar weil sie eben nicht lösbar sind und damit liegen auch diese natürlich nicht in p diese besonders schweren
- probleme beziehungsweise die unlösbaren probleme die gemeinsam wiederum bilden noch einmal eine besondere klasse die sich aber teilweise mit mp überschneidet
- nämlich dass es die klasse np schwer in deutschland hört man manchmal auch den begriff np hart das ist aber tatsächlich nur eine schlechte
- übersetzung des englischen begriffs np hart im englischen heißt er an der stelle schwer also von daher es gibt das sind
- die einfachen probleme es gibt mp das sind die probleme die ich nicht so ohne weiteres lösen kann und es gibt eben mp schwer das ist ein teil von np das sind
- nämlich die besonders schwierigen probleme plus zusätzlich noch die gar nicht lösbaren problemen interessant ist jetzt die frage oder
- interessant ist jetzt die schnittmenge zwischen np und mp schwer also die haben ja eben schon gesagt np schwer enthält nur die besonders schwierigen probleme
- aus np wenn ich aber jetzt np schwer auf die probleme beschränke die überhaupt lösbar sind also wenn ich die nicht lösbaren mal außen vor lassen dann habe
- ich die schnittmenge zwischen np und mp schwer und diese schnittmenge hat noch mal einen eigenen namen die heißt nämlich np vollständig oder im
- englischen np komplett und es gibt eine besonderheit mit dieser schnittmenge nämlich alle probleme aus np lassen sich auf probleme aus mp vollständig
- zurückführen oder wie man in der theoretischen informatik sagt sie lassen sich auf probleme aus np vollständige reduzieren
- das bedeutet wenn es ein einziges problem in mp vollständig gibt für dass es gelingt eine laufzeit an einem eine lösung zu finden einen algorithmus zur
- lösung zu finden der polen um alle laufzeit hat also wenn es gelingt ein einziges problem aus mp vollständig sozusagen in guter laufzeit zu lösen
- dann lassen sich automatisch alle probleme aus np ebenfalls in guter laufzeit lösen weil jedem alle probleme auf aus np auf ein problem aus mp
- vollständig zurückführbar sind das bedeutet auch dass jedes problem in mp vollständig auf jedes andere problem aus mp vollständig zurück für wahr ist und
- das ist der grund warum es eben genügt ein einziges dieser probleme zu lösen weil ich eben wenn ich ein einziges mp vollständiges problem in polemischer
- laufzeit gelöst habe alle anderen np vollständigen probleme auch lösen kann und in pully nominaler laufzeit und damit eben alle probleme in npd die sich
- in irgendeiner form auf die mp vollständigen probleme zurückführen lassen eben auch in poley nominaler laufzeit lösen kann insofern ist das ein
- ganz spannendes feld eben zu versuchen einen eines dieser np vollständigen probleme in poley nominaler laufzeit zu lösen
- die frage an der stelle ist einfach nur gibt es denn überhaupt eine polymere lösung für ein beliebiges np vollständiges problem und diese frage
- ist offen die ist ungeklärt die ist unbewiesen das ist bisher niemandem gelungen eine lösung zu finden dass es bisher auch niemandem gelungen zu
- beweisen dass es eine solche lösung geben muss oder zu zeigen dass es eine solche lösung nicht geben kann und wenn man das ganze aus ein bisschen
- anderer perspektive betrachtet dann könnte man sagen in dem moment wo es gelingt ein mp vollständiges problem in poley nominal
- zeit zu lösen weil dann eben alle np probleme in poley nominal zeit lösbar wären dann würde das ja bedeuten als konsequenz dass die komplexität klasse p
- und die komplexität klasse np eben identisch sind und das ist eben genau das was unbekannt ist was es bisher nicht geklärt ist womit man übrigens
- sehr sehr viel geld verdienen kann dieses problem op und mp identisch sind oder nicht das gehört zu den sogenannten millennium problemen des clay instituts
- und da ist ein hohes preisgeld darauf ausgesetzt also wer am wochenende zum beispiel noch nichts vor hat und sich in dieser richtung irgendwie betätigen mag
- kann darüber ja gerne mal nachdenken vielleicht hat ja die eine oder der andere eine geniale idee so dass er also die klasse p und die klasse np und diese
- np vollständig klasse die also sozusagen diese besonderen probleme enthält die sozusagen der ursprung für alle anderen probleme aus np sind die gucken wir uns
- morgen noch mal etwas näher im detail für heute möchte ich mich bedanken dass wir mit dabei gewesen seid ich hoffe ich habe das video gefallen wenn ja dann
- würde ich mich freuen wenn ihren daumen nach oben da last und abonniert den kanal falls ihr das noch nicht gemacht habt und damit er über neue videos von
- youtube benachrichtigt werden denkt daran die glocke zu aktivieren ansonsten wünsche ich euch noch einen schönen donnerstag passt gut auf euch
- auf bleibt gesund macht gut und dann sehen wir uns morgen wieder
Zum Nachlesen
KomplexitätKomplexe Ordnungen sind ständig im Wandel. Die Zunahme von Komplexität wird als „positive“, die Abnahme als „negative“ Komplexifikation bezeichnet. [A 9].
KomplexitätstheorieDie Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die …
InformatikAls einfache Rechengeräte leisteten Abakus und später der Rechenschieber unschätzbare Dienste. 1641 konstruierte Blaise Pascal eine mechanische …
ProblemInhaltsverzeichnis · 1 Allgemeines · 2 Definitionen · 3 Problemklassen. 3.1 Lösbarkeit; 3.2 Zerlegbarkeit; 3.3 Verwandtheit · 4 Wissenschaften. 4.1 Denkpsychologie …