Heu­te ist ein Beweis für P≠NP auf­ge­taucht und Infor­ma­ti­ker in aller Welt sind irgend­wie auf­ge­regt. Aber was bedeu­ten P und NP?

Einleitung

Ist ein Pro­blem in P oder NP? - das ist eine Fra­ge von deren Ant­wort abhän­gen kann, ob die Berech­nung der exak­ten Lösung ein paar Stun­den dau­ert oder so lan­ge wie das Uni­ver­sum alt ist. Ein Bei­spiel aus dem All­tag: Man will über den Tag ver­teilt noch eini­ge Sachen erle­di­gen: Buch in der Biblio­thek abge­ben, was Essen, ein paar Sachen ein­kau­fen, sich mit jeman­dem tref­fen. All die­se Din­ge fin­den an ver­schie­de­nen Orten statt. Wie ist die kür­zes­te Rou­te von der eige­nen Woh­nung zu all die­sen Orten und wie­der zurück? wei­ter…