Ich habe neulich auf dieser Website herumgespielt : http://regexcrossword.com/, und ich habe mich gefragt, wie ich es am besten lösen kann.
Können Sie das folgende Problem in Polynomzeit lösen oder ist es NP-schwer?
Suchen Sie bei einem NxM-Raster mit N regulären Ausdrücken für die Spalten und M für die Zeilen eine beliebige Lösung für das Raster, sodass alle regulären Ausdrücke erfüllt sind, oder sagen Sie, dass keine Lösung vorhanden ist.
complexity-theory
np-hard
regular-expressions
Glen Takahashi
quelle
quelle
Antworten:
Das Problem ist NP-schwer.
Wir zeigen dies, indem wir die Scheitelpunktabdeckung reduzieren:
Wir übersetzen dies in ein reguläres Kreuzworträtsel mit Spalten und|E|+1 Zeilen wie folgt:|V|
Alle Spalten mit Ausnahme der ersten entsprechen einer Kante. Sie erhalten eine Regex .0∗1(0|1)∗
Alle Zeilen entsprechen einem Eckpunkt. Sie erhalten einen regulären Ausdruck, mit dem Sie entweder schreiben können
ein in der ersten Spalte und jede Spalte entspricht einer Kante, die auf diesen Knoten fällt, und Nullen in allen anderen Spalten, oder1
Schließlich zählt die erste Spalte die Größe der Scheitelpunktabdeckung. Es wird ein regulärer Ausdruck erzeugt, der höchstens zulässt .k
Die Entsprechung zwischen Lösungen für das Regex-Kreuzworträtsel und Vertex-Cover sollte offensichtlich sein.
Beispiel:
Suchen Sie eine Scheitelpunktabdeckung der Größe 2 für das folgende Diagramm:
quelle
Die Frage bleibt NP-vollständig, auch wenn alle regulären Ausdrücke gleich sind. http://arxiv.org/abs/1411.5437
quelle