Czy krzyżówki wyrażeń regularnych są trudne NP?

Pewnego dnia wygłupiałem się na tej stronie: http://regexcrossword.com/ i zastanawiałem się, jaki był najlepszy sposób rozwiązania tego problemu.

Czy potrafisz rozwiązać następujący problem w czasie wielomianowym, czy jest to trudne NP?

Biorąc pod uwagę siatkę NxM z N wyrażeniami regularnymi dla kolumn i M dla wierszy, znajdź dowolne rozwiązanie siatki, tak aby wszystkie wyrażenia regularne były spełnione, lub powiedz, że nie istnieje żadne rozwiązanie.

Problem jest trudny NP.

Pokazujemy to poprzez zmniejszenie pokrycia wierzchołków:

$G=(V,E)$$k$$V' \subseteq V$$k$$E$$V'$

$|E|+1$$|V|$

$0^*1(0|1)^*$

Wszystkie wiersze odpowiadają wierzchołkowi. Dostają regex, który pozwala na pisanie albo

• $1$

• $0^*$

$k$

Zgodność między rozwiązaniami krzyżówki wyrażeń regularnych a okładkami wierzchołków powinna być oczywista.

Przykład:

Znajdź okładkę wierzchołka o rozmiarze 2 dla następującego wykresu:

$V_A = 0^* \big| 10110$

$V_B = 0^* \big| 11101$

$V_C = 0^* \big| 10011$

$V_D = 0^* \big| 11000$

$Counter = 0^* \big| 0^*10^* \big| 0^*10^*10^*$

$E_1 = 0^*1(0|1)^*$

$E_2 = 0^*1(0|1)^*$

$E_3 = 0^*1(0|1)^*$

$E_4 = 0^*1(0|1)^*$

$V_A$$V_D$$Counter$$E_1$$E_4$

$V_A,V_B$$V_C,V_B$

$Counter$$0^* \big| 0^*10^*$

Pytanie pozostaje NP-kompletne, nawet jeśli wszystkie wyrażenia regularne są równe. http://arxiv.org/abs/1411.5437