Zeitungsartikel über „P=NP?“ am 26.08.19

Heute haben wir im Unterricht den Zeitungsartikel aus der „Zeit Online“ gelesen, welchen wir als Hausaufgabe hätten lesen sollen. Zum download kommt ihr hier.

Beim lesen haben wir uns darauf geeinigt, dass wir 10k/2 als „Wurzel aus 10 hoch k“ lesen.
Was ich in dem Artikel als wichtig empfand sind folgende Punkte:
– Es gibt schwierigere Probleme als NP-Vollständige Probleme. Das heißt, sie liegen außerhalb von P und NP.
– Im Artikel wurde auch das Problem des Handelsreisenden angesprochen, hier auf inf-schule etwas weiter unten, dieses haben wir auch kurz angesprochen, aber noch nicht ausführlich, da wir es später besprechen. Herr Karp erwähnte dann ein ähnliches, praxisrelevantes Problem: Das Bestücken von Leiterplatinen. Hier wird es immer schwerer effiziente Lösungen zu finden, je komplexer die Platine wird. Es gibt Programme, die nahe an die effizienteste Lösung kommen, aber eben nur nahe.
– Im Artikel wurde auch wieder SAT erwähnt und dargelegt was reduzieren von NP-Problemen auf ein NP Vollständiges Problem bedeutet. Es bedeutet, dass wenn man Probleme in NP auf ein schwereres Problem in NP reduzieren kann, dann kann all diese Probleme lösen, wenn man das schwerere Problem lösen kann. Da man alle Probleme in NP auf SAT reduzieren kann, heißt das, dass man alle Probleme in NP in polynomialer Zeit lösen kann, wenn man SAT in polynomialer Zeit lösen kann.
– Faktorisierung, das Prinzip welches aktuell bei der Verschlüsselung benutzt wird, liegt in NP und lässt sich auch reduzieren. Dadurch sind die Verschlüsselungen durch Faktorisierung nur so lange sicher bis es eine Lösung eines Problems gibt, auf das sich die Faktorisierung reduzieren lässt.

Als Hausaufgabe haben wir auf, NP Vollständige Probleme auf inf-schule zu lesen und versuchen zu verstehen.

Schreibe einen Kommentar