Wie in diesem aktuellen XKCD-Strip und diesem aktuellen Blog-Post zu sehenVon Peter Norvig (und einer Slashdot-Geschichte mit letzterem) ist "Regex Golf" (das besser als das Problem der Trennung regulärer Ausdrücke bezeichnet werden könnte) das Rätsel, den kürzestmöglichen regulären Ausdruck zu definieren, der jedes Wort in Satz A und kein Wort in Satz A akzeptiert Set B. Norvigs Beitrag enthält einen Algorithmus zur Generierung eines relativ kurzen Kandidaten. Er merkt an, dass sein Ansatz die Lösung eines NP-vollständigen Set-Cover-Problems beinhaltet. Er weist jedoch auch darauf hin, dass sein Ansatz nicht alle möglichen regulären Ausdrücke berücksichtigt. und natürlich ist er nicht notwendigerweise der einzige Algorithmus, daher kann nicht garantiert werden, dass seine Lösungen optimal sind, und es ist auch möglich, dass ein anderer Algorithmus mit sicherer Polynomzeit äquivalente oder bessere Lösungen findet.
Der Vollständigkeit halber und um zu vermeiden, dass die Optimierungsfrage gelöst werden muss, würde die natürlichste Formulierung für die Trennung regulärer Ausdrücke lauten:
Gibt es bei zwei (endlichen) Mengen und von Zeichenketten über ein Alphabet einen regulären Ausdruck der Länge , der jede Zeichenkette in akzeptiert und jede Zeichenkette in ablehnt ?
Ist etwas über die Komplexität dieses speziellen Trennungsproblems bekannt? (Da ich und als endliche Mengen von Zeichenfolgen angegeben habe, ist der natürliche Größenbegriff für das Problem die Gesamtlänge aller Zeichenfolgen in und ; dies überflutet jeden Beitrag von ). Es scheint sehr mir wahrscheinlich , dass es ist NP-vollständig (und in der Tat würde ich die Reduktion auf eine Art Abdeckung Problem zu sein erwarten) , aber ein paar Recherchen haben nicht aufgedreht etwas besonders nützlich.
quelle
Antworten:
Unter der Annahme der TCS-Variante von Regex ist das Problem in der Tat NP-vollständig.
Wir gehen davon aus, dass unsere Regexes enthalten
und sonst nichts. Die Länge eines regulären Ausdrucks ist definiert als die Anzahl der Zeichen aus . Wie im Comic betrachten wir einen regulären Ausdruck, um ein Wort zu finden, wenn es einem Teil des Wortes entspricht. (Das Ändern einer dieser Annahmen sollte nur die Komplexität der folgenden Konstruktion beeinflussen, nicht jedoch das allgemeine Ergebnis.)Σ
Wie in den Kommentaren erläutert, ist es in NP unkompliziert (überprüfen Sie einen RE-Kandidaten, indem Sie ihn in eine NFA übersetzen und dies für alle Wörter von und B ausführen ).EIN B
Um die NP-Härte zu zeigen, reduzieren wir die Set-Abdeckung:
Wir übersetzen eine Eingabe für Set Cover in eine für Regex Golf wie folgt:
Diese Reduktion ist offensichtlich in P und die Äquivalenz ist auch ziemlich einfach zu sehen:
quelle