Throwback Tuesday #4: Wenn der Busy Beaver erzählt …

Einen nicht ganz ernst gemeinten Vorschlag zur Erweiterung der Komplexitätstheorie lesen wir in einem Beitrag von Klaus Kneuper und Thomas Leineweber für den Busy Beaver Nr. 82 (Februar 1997).

Von den Autoren werden die neuen Klassen T, NT und NTC eingeführt – das sind die Klassen der trivialen, der nichttrivialen und die der schwersten Probleme. Die Motivation für diese neuartige Theorie gründen die Autoren auf der persönlichen Erfahrung, dass angeblich triviale Beweise nicht so trivial sind, wie es die Dozenten in Vorlesungen behaupten. Daher soll eine exakte Definition der Klasse trivialer Probleme diese genauer bestimmen und von von den anderen Klassen leichter unterscheidbar machen:

Triviale Probleme und die Klasse T

Definition: Sei M ein beliebieger Stunden aus der Klasse EBOC (mit einem Blatt Papier und ohne Vordiplom). Ein Problem P heißt dann trivial, P ∈ T, wenn es von M unter Zuhilfenahme einer nicht näher bestimmten Buches innerhalb eines Tages auf dem Blatt Papier gelöst werden kann *

*Dabei gilt es natürlich zu beachten, dass die Auswahl des Buches wiederum eiin nichttriviales Problem darstellt!