Was liegt eigentlich in der NP-Schublade?
Vielleicht ist euch aufgefallen, dass ich bisher von keinem Problem gesprochen habe, das in der NP-Schublade liegt. Ist diese Schublade leer? Bisher schon. Denn wir kennen (noch?) keine Probleme, die in dieser Schublade liegen. Bis auf eine Ausnahme: Ein künstliches Problem ohne praktische Relevanz. Wozu? Dieses Problem hat sich 1975 Richard Ladner ausgedacht, um eben diese Frage zu beantworten, ob die NP-Schublade leer ist. Er hat also ein Problem entworfen, das weder in die P, noch in die NPC Schublade gehört, aber eben trotzdem zur Klasse NP. Natürlich nur, wenn P≠NP (sonst schütten wir ja eh alle drei Schubladen zusammen). Es gibt aber auch in der Praxis ein paar Probleme, von denen man vermutet, dass sie in dieser Schublade liegen. Zum Beispiel die Primfaktorzerlegung: die Darstellung einer natürlichen Zahl als Produkt aus Primzahlen. Interessant ist das vor allem für Verschlüsselungsverfahren in der Kryptographie.
Wie lösen wir denn nun die schweren Probleme?
Natürlich nützt es nix zu sagen “Joa, das Problem ist schwer, da können wir jetzt leider nix machen”. So denkt ein Informatiker nicht. Stattdessen müssen wir uns eben ein Paar Tricks und Kniffe einfallen lassen — aber von denen berichte ich euch ein anderes Mal.
Beitrag auf BioinfoWelten lesen.
Kommentare (2)