Sind Regex-Kreuzworträtsel NP-hart?

13

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.

Glen Takahashi
quelle
Ich habe mir die Seite noch nicht angesehen, aber Fragen mit Regexes sind in der Regel vollständig PSPACE, eine Klasse, die mindestens so schwer ist wie NP
jmite
1
@jmite Das Erraten von Zeichenfolgen, die zu einigen regulären Ausdrücken passen, ist "einfach", da wir keine globalen Eigenschaften des regulären Ausdrucks ableiten müssen. In der Tat denke ich, dass das Problem in NP liegt (siehe Kommentar unter der Antwort von FrankW.)
Raphael

Antworten:

11

Das Problem ist NP-schwer.

Wir zeigen dies, indem wir die Scheitelpunktabdeckung reduzieren:

Bei einem Graphen und einer Schwelle k gibt es eine Teilmenge V V der Kardinalität höchstens k , so dass jede Kante in EG=(V,E)kVVkE auf mindestens einen Knoten in fällt ?V

Wir übersetzen dies in ein reguläres Kreuzworträtsel mit Spalten und|E|+1Zeilen wie folgt:|V|

Alle Spalten mit Ausnahme der ersten entsprechen einer Kante. Sie erhalten eine Regex .01(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

  • 0

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:

https://i.imgur.com/TY6sjjV.png

VA=0|10110

VB=0|11101

VC=0|10011

VD=0|11000

Counter=0|010|01010

E1=01(0|1)

E2=01(0|1)

E3=01(0|1)

E4=01(0|1)

VAVDCounterE1E4

VA,VBVC,VB

Counter0|010

FrankW
quelle
2
Da wir a) polynomial bemessene NFA für die regulären Ausdrücke berechnen können sowie b) die Lösung und c) (linear bemessene) Berechnungen aller NFAs und d) (in polynomialer Zeit) überprüfen können, ob die Berechnungen zu den erratenen Wörtern passen, Das Problem ist auch in NP.
Raphael
2

Die Frage bleibt NP-vollständig, auch wenn alle regulären Ausdrücke gleich sind. http://arxiv.org/abs/1411.5437

Steve
quelle