Monadische Erweiterungen von monadic NP

Abstract

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).

In 1974 Fagin showed in his groundbreaking work, that the complexity class NP corresponds with existentiel second order logic. An easy and manageable fragmentof existentiel second order logic is monadic NP. Fagin called monadic NP to be a '... training ground for attacking the problems in their full generality'. This work is discussing two ways of monadic extensions of monadic NP. The first part handles with weak built-in relations. A built-in relation B is called weak, if: monadic NP + B + polynomiel padding \neq NP.Two new classes of weak built-in relations (infinitly divisible-and packable built-in relations) are introduced. The main result of this part is a classificationof all known weak built-in relations, by means of these two classes. The second part of this work deals with monadic NP. The positive first order closure of monadic NP (brief: PFO(monNP)) is of special interest. The main result of thispart is the fact, that non-k-colourability (k=>3) is not expressible in PFO(monNP).