Richard Ladner stellte 1975 in seinem Aufsatz "One the Strucure of
Polynomial Time Reducibility" ein zunächst verblüffendes
Ergebnis vor: Falls P ungleich NP ist, dann muss es
in NP - P Probleme geben, die nicht NP-vollständig sind.
In meinem Vortrag im Rahmen des
Küchenkolloquiums
der Henke-WG habe ich die zum Verständnis dieses Satzes notwendigen
Begriffe (Reduzierbarkeit, Orakel-Turing-Maschinen, ...) geklärt und
anschließend den ursprünglichen Beweis von Ladner (inzwischen
gibt es einen Haufen Beweise anderer Theoretiker, die sich aber in ihrem
Wesen nicht vom Original-Beweis unterscheiden) an der Tafel durchgeführt.
Zum Verständnis der Ausführungen sei wenigstens ein
Grundverständnis von Berechenbarkeit und Komplexität empfohlen.
