DAS P‑NP-Pro­blem — eine wenig bekann­te Kar­di­nal­fra­ge

Hal­lo Ihr Lie­ben,

heu­te Mit­tag habe ich end­lich mal wie­der einen Vor­trag im Rota­ry-Club Frank­furt am Main Frie­dens­brü­cke hal­ten dür­fen. Nach­dem ich dort bis­her über reli­giö­se und poli­ti­sche The­men vor­ge­tra­gen hat­te, habe ich mir dies­mal ein The­ma aus mei­ner urei­ge­nen Dis­zi­plin her­aus­ge­sucht – der Infor­ma­tik.

Dabei geht es um nicht weni­ger als die Kar­di­nal­fra­ge der theo­re­ti­schen Infor­ma­tik schlecht­hin: das soge­nann­te “P‑NP-Pro­blem”. Dahin­ter ver­birgt sich die Fra­ge, ob man mit Hil­fe for­ma­ler mathe­ma­ti­scher Logik bewei­sen kann, dass es Pro­blem­stel­lun­gen gibt, für die das pro­gramm­ge­steu­er­te Berech­nen einer Lösung sub­stan­zi­ell auf­wän­di­ger ist als, das Über­prü­fen eines vor­ge­schla­ge­nen Lösungs­kan­di­da­ten dar­auf­hin, ob er auch wirk­lich eine Lösung des betrach­te­ten Pro­blems ist.

Das klingt jetzt reich­lich abs­trakt. Aber die Tat­sa­che, dass die­se Fra­ge bis heu­te unge­klärt ist, hat eine erheb­li­che Bedeu­tung für die Daten­si­cher­heit in unse­rer infor­ma­ti­ons­tech­no­lo­gisch durch­drun­ge­nen Welt. Die Wesent­li­chen der heu­te im elek­tro­ni­schen Daten­ver­kehr ver­wen­de­ten Ver­schlüs­se­lungs­ver­fah­ren set­zen näm­lich genau auf eben jene unbe­wie­se­ne Annah­me, dass das Berech­nen der ver­wen­de­ten Schlüs­sel ungleich schwe­rer ist, als das Ent­schlüs­seln mit Hil­fe eines gege­be­nen Schlüs­sels. Wäre dem näm­lich nicht so, dann wären die­se Chif­frie­rungs­ver­fah­ren alle­samt wert­los und unse­re ver­schlüs­sel­ten Daten damit unge­fähr so gut gegen die Kennt­nis­nah­me durch Unbe­fug­te gesi­chert, wie beim Ver­sen­den einer Post­kar­te. Unse­re Welt wäre also nicht mehr die­sel­be, wenn es jeman­dem gelän­ge, den bis heu­te aus­ste­hen­den Beweis dafür anzu­tre­ten, dass Über­prü­fen eben doch nicht sub­stan­zi­ell schwe­rer ist als Berech­nen. Aus genau die­sem Grund gehört das P‑NP-Pro­blem denn auch zu den soge­nann­ten „Mill­en­ni­um­pro­ble­men“, auf deren Lösung das Clay Mathe­ma­tics Insti­tu­te einen Preis in Höhe von nicht weni­ger als $ 1.000.000,00 aus­ge­lobt hat.

Inter­es­se geweckt? Na klar: tech­no­kra­ti­sches Gela­ber hin oder her – etwas, das so viel Koh­le wert ist, muss ein­fach inter­es­sant sein…

Na dann: die text­li­che Aus­ar­bei­tung des Vor­trags fin­det Ihr als PDF-Datei unter fol­gen­dem Link:

http://www.kornfamily.de/daniel/Rotary/P‑NP-Problem.pdf

Das MP4-Video mit den ani­mier­ten Vor­trags­fo­li­en könnt Ihr hin­ge­gen hier betrach­ten:

Mei­net­we­gen könnt Ihr das ger­ne mal wie­der als abge­dreh­ten Nerd-Kram dif­fa­mie­ren. Ähn­lich wie für mei­ne Man­del­brot­men­gen-Blog­se­rie gilt aber letzt­lich auch hier: es ist nicht wirk­lich leicht, die­se Art von Mate­rie für den nicht-Infor­ma­ti­ker gleich­zei­tig anschau­lich und den­noch tief­grün­dig genug zu ver­mit­teln, um Bedeu­tung und Trag­wei­te des zen­tra­len Gegen­stands wirk­lich erkenn­bar wer­den zu las­sen.

So oder so wün­sche ich viel Spaß beim Lesen und/oder Betrach­ten. Kom­men­ta­re sind – wie immer – jeder­zeit ger­ne erwünscht.

Alles Lie­be

Dani­el

Kommentiere diesen Beitrag als Erste(r)

Kommentar verfassen

Letz­te Bei­trä­ge

Kate­go­ri­en

%d Bloggern gefällt das: