Komplexität und Automaten

Komplexitätstheorie: NP-vollständige Mengen

Alle bekannten NP-vollständigen Mengen besitzen die bemerkenswerte Eigenschaft, dass sie zueinander isomorph sind. Das heißt, dass es für solche Mengen A und B eine polynomialzeitberechenbare und polynomialzeitinvertierbare Bijektion f gibt, sodass x genau dann ein Element von A ist, wenn f(x) ein Element von B ist. Damit handelt es sich bei den bekannten NP-vollständigen Mengen bis auf Isomorphie um ein und dieselbe Menge.

Bisher ist es jedoch nicht gelungen, diese Aussage für alle NP-vollständigen Mengen zu beweisen. Man sucht daher schwächere Eigenschaften, die sich für alle NP-vollständigen Mengen nachweisen lassen. Beispielsweise kann man zeigen, dass sich jede unendliche NP-vollständige Menge in eine beliebige Anzahl NP-vollständiger Mengen aufteilen lässt. Damit besitzen alle NP-vollständigen Mengen ein gewisses Maß an Redundanz. Ziel unserer aktuellen Forschung ist es, weitere Eigenschaften zu finden, die sich für alle NP-vollständigen Mengen nachweisen lassen.

 

Automaten und Formale Sprachen: Dot-Depth-Problem

Reguläre Sprachen lassen sich durch reguläre Ausdrücke beschreiben. Letztere sind aus Buchstaben und den Operationen Vereinigung, Konkatenation und Iteration aufgebaut. Man kann auch den Schnitt und das Komplement als Operationen zulassen, ohne die regulären Sprachen zu verlassen. Verzichtet man auf die Iteration, so erhält man sternfreie reguläre Ausdrücke. So beschreibbare Sprachen nennt man sternfreie reguläre Sprachen.

Die Aufgabe, eine Sprache durch einen sternfreien regulären Ausdruck mit einer minimalen Anzahl geschachtelter Konkatenationen und Komplemente zu beschreiben, ist als Dot-Depth-Problem bekannt. Bisher ist offen, ob dieses Problem algorithmisch lösbar ist. Um sich diesem sehr schwierigen Problem dennoch zu nähern, versucht die aktuelle Forschung das Dot-Depth-Problem für Teilklassen sternfreier regulärer Sprachen zu lösen.

 

Ansprechpartner: Christian Glaßer