Les mots croisés d'expression régulière sont-ils durs en NP?

Je me moquais de l'autre jour sur ce site Web: http://regexcrossword.com/ et cela m'a fait me demander quelle était la meilleure façon de le résoudre.

Pouvez-vous résoudre le problème suivant en temps polynomial ou est-il NP-difficile?

Étant donné une grille NxM avec N expressions régulières pour les colonnes et M pour les lignes, trouvez une solution à la grille telle que toutes les expressions régulières soient satisfaites, ou dites qu'aucune solution n'existe.

Le problème est NP-difficile.

Nous le montrons en réduisant la couverture des sommets:

Etant donné un graphe et un seuil k , existe-t-il un sous-ensemble V ′ ⊆ V de cardinalité au plus k , de sorte que chaque front dans E est incident avec au moins un nœud dans V ′ ?$G=(V,E)$$k$$V' \subseteq V$$k$$E$$V'$

Nous traduisons cela en mots croisés regex avec colonnes et | V | lignes comme suit:$|E|+1$$|V|$

Toutes les colonnes, à l'exception de la première, correspondent à un bord. Ils obtiennent une expression régulière .$0^*1(0|1)^*$

Toutes les lignes correspondent à un sommet. Ils obtiennent une expression régulière qui permet d'écrire soit

• un dans la première colonne et chaque colonne correspondant à un bord incident à ce nœud et des zéros dans toutes les autres colonnes, ou$1$

• $0^*$

Enfin, la première colonne compte la taille de la couverture des sommets. Il obtient une expression régulière, qui permet au plus unités.$k$

La correspondance entre les solutions aux mots croisés d'expression rationnelle et les couvertures de sommets devrait être évidente.

Exemple:

Trouvez une couverture de sommet de taille 2 pour le graphique suivant:

$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^*$

La question reste NP-complète même lorsque toutes les expressions régulières sont égales. http://arxiv.org/abs/1411.5437