Monadische Erweiterungen von monadic NP

Fagin zeigt in seiner bahnbrechenden Arbeit, dass die Komplexitätsklasse NP mit der logischen Sprache 'existentielle Logik zweiter Ordnung' identifiziert werden kann. Ein einfaches und daher greifbares Fragment dieser Sprache ist monadic NP. Fagin bezeichnet monadic NP als '...training ground for attacking the problems in their full generality'. In dieser Arbeit werden zwei Arten von monadischen Erweiterungen von monadic NP untersucht. Der erste Teil beschäftigt sich mit schwachen built-in Relationen.Einebuilt-in Relation B heißt schwach, falls: monadic NP + B + polynomielles Padding neq NP.Es werden zwei neue Klassen schwacher built-in Relationen (unendlich teilbare-und verpackbare built-in Relationen) eingeführt. Hauptergebnis dieses Teils ist eine Klassifizierung aller bekannten schwachen built-in Relationen mittels dieser beiden Klassen. Im zweiten Teil dieser Arbeit werden monadische Abschlüsse von monadic NP betrachtet. Besonderes Interesse gilt dabei den positiven Abschluss erster Ordnung von monadic NP (kurz: PFO(monNP)). Hauptergebnis dieses Teils ist die Aussage, dass nicht-k-Färbbarkeit (k=>3) nicht ausdrückbar ist in PFO(monNP).

Das moderne Buch: Harry Graf Kesslers Ästhetik der Lebenskunst im Spiegel der Großherzog Wilhelm Ernst Ausgabe deutscher Klassiker

Die Großherzog Wilhelm Ernst Ausgabe deutscher Klassiker wurde seit 1904 bis in die Zwanziger Jahre hinein im Insel Verlag in Leipzig publiziert. Die Buchreihe hat nicht nur für den Verlag und die Druckerei Poeschel in der sie gedruckt wurde eine ganze Reihe von Neuerungen nach sich gezogen, auch für den deutschen Buchmarkt hat die Klassikerausgabe einen Meilenstein bedeutet. Sie hat einige Eigenschaften des Taschenbuches vorweggenommen. Sie orientierte sich an der Qualität bibliophiler Buchpublikationen, aber war dennoch preislich erschwinglich. Zeitgenössische Klassikerausgaben erschienen zumeist mit einem Kommentar. Nicht so die Großherzog Wilhelm Ernst Ausgabe. Der Text wurde zwar von führenden Wissenschaftlern editiert, aber sie war dennoch unkommentiert. Der Text war in einer Jenson-Antiqua gesetzt obwohl die Debatte um individuell gestaltete Künstlerschriften und die Diskussion um die als deutsche Schrift begriffene Fraktur unter den wichtigsten Protagonisten des deutschen Buchgewerbes ihren Höhepunkt noch nicht erreicht hatte. Ziel für die Klassikerausgabe war darüber hinaus, das zur Jahrhundertwende leicht angestaubte Image der Stadt Weimar aufzupolieren. Über das Patronat des Großherzogs hinaus hätte man die Gewinne aus dem Verkauf der Bücher der Permanenten Ausstellung für die Anschaffung von modernen Kunstobjekten zur Verfügung stellen wollen, die unter der Leitung von Harry Graf Kessler stand. Sieht man den Inhalt der Werke der in der Klassikerreihe erschienen Dichter Goethe, Schiller und Körner in einem ästhetischen Kontext mit dem der Philosophen Schopenhauer und Kant, wird im Spiegel der Formalästhetik der Klassikerausgabe Graf Kesslers Bildungs- und Kulturbegriff erkennbar, der sich in den Jahren nach der Jahrhundertwende zu seinem Lebenskunstideal verdichtete. Der zerrütteten Existenz der Zeitgenossen, wie Friedrich Nietzsche sie beschrieben hatte, sollte der Inhalt der Ausgabe in seiner modernen Form eine moderne Wertehaltung entgegensetzen. Die Lektüre der Klassiker sollte den deutschen Philister „entkrampfen“ und ihm ein Stück der verloren geglaubten Lebensfreude wieder zurück bringen, in dem dieser auch die Facetten des Lebensleids als normal hinnehmen und akzeptieren lernte. Die Klassikerausgabe repräsentierte aus diesem Grund auch den kulturellen und politischen Reformwillen und die gesellschaftlichen Vorstellungen die der Graf für ein modernes Deutschland als überfällig erachtete. Die Buchreihe war aus diesem Grund auch ein politisches Statement gegen die Beharrungskräfte im deutschen Kaiserreich. Die Klassikerreihe wurde in der buchhistorischen Forschung zwar als bedeutender Meilenstein charakterisiert und als „wichtiges“ oder gar „revolutionäres“ Werk der Zeit hervorgehoben, die Ergebnisse der Forschung kann man überspitzt aber in der Aussage zusammenfassen, dass es sich bei der Großherzog Wilhelm Ernst Ausgabe um einen „zufälligen Glückstreffer“ deutscher Buchgestaltung zu handeln scheint. Zumindest lassen die Aussagen, die bisher in dieser Hinsicht gemacht wurden, keine eindeutige Einordnung zu, außer vielleicht der, dass die Klassiker von der englischen Lebensreform inspiriert wurden und Henry van de Velde und William Morris einen Einfluss auf ihre äußere Form hatten. Gerade die Gedankenansätze dieser Beiden nutzte Graf Kessler aber für eigene Überlegungen, die ihn schließlich auch zu eigenen Vorstellungen von idealer Buchgestaltung brachten. Da für Kessler auch Gebrauchsgegenstände Kunst sein konnten, wird das Konzept der Klassikerausgabe bis zur Umsetzung in ihrer `bahnbrechenden´ Form in das ideengeschichtliche und ästhetische Denken des Grafen eingeordnet. Die Klassiker werden zwar in buchhistorischen Einzeluntersuchungen bezüglich ihrer Komponenten, dem Dünndruckpapier, ihrem Einband oder der Schrifttype exponiert. In buchwissenschaftlichen Überblicksdarstellungen wird ihr Einfluss hingegen weniger beachtet, denn verschiedene Kritiker bezogen sie seit ihrem ersten Erscheinen nicht als deutsches Kulturgut mit ein, denn sie lehnten sowohl die englischen Mitarbeiter Emery Walker, Edward Johnston, Eric Gill und Douglas Cockerell wie auch ihre Gestaltung als „welsche“ Buchausgabe ab. Richtig ist, die Großherzog Wilhelm Ernst Ausgabe hatte dieselbe Funktion wie die von Graf Kessler in Weimar konzipierten Kunstausstellungen und die dortige Kunstschule unter der Leitung seines Freundes Henry van de Velde. Auch das für Weimar geplante Theater, das unter der Leitung von Hugo von Hofmannsthal hätte stehen sollen und die Großherzog Wilhelm Ernst Schule, hätten dieselben Ideen der Moderne mit anderen Mitteln transportieren sollen, wie die Großherzog Wilhelm Ernst Ausgabe deutscher Klassiker.