Matthias Hagen: Komplexität monotoner DNF- und Isomorphie-Probleme

Wie schwer ist es, Primimplikanten oder eine minimale Disjunktive Normalform (DNF) für Boolesche Formeln zu finden oder die Isomorphie von Formeln zu testen? Wir untersuchen diese Probleme für monotone Formeln und vergleichen die Resultate mit solchen für beliebige Formeln.

Für die im Zusammenhang mit DNFen stehenden Probleme unterscheiden sich die Ergebnisse für monotone und beliebige Formeln stark. Wir zeigen, dass es DP-vollständig ist, von einem Monom festzustellen, ob es Primimplikant einer gegebenen Formel ist. Die gleiche Frage kann im monotonen Fall in L entschieden werden.

Wir zeigen die PP-Vollständigkeit der Frage, ob eine gegebene monotone Formel eine DNF der Größe höchstens k besitzt. Ist k unär gegeben, so fällt das Problem sogar in die Klasse coNP. In einer Arbeit von Umans (2001) wird ein ähnliches Problem für beliebige Formeln als Σ2p-vollständig charakterisiert.

Wir zeigen, dass die Berechnung der minimalen DNF einer monotonen Formel genau dann in Output-Polynomialzeit durchgeführt werden kann, wenn P = NP gilt. Ein analoges Resultat ist für beliebige Formeln bisher nicht bekannt.

Im Gegensatz zu den DNF-Problemen stellt sich der Isomorphietest für monotone Formeln als genauso schwer wie der für beliebige Formeln heraus. Dies widerlegt eine Vermutung von Reith (2003).