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

13

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.

Glen Takahashi
la source
Je n'ai pas encore regardé le site, mais les questions avec Regexes ont tendance à être complètes sur PSPACE, une classe au moins aussi difficile que NP
jmite
1
@jmite Il est "facile" de deviner des chaînes qui correspondent à certaines expressions régulières, car nous n'avons pas à dériver une propriété globale de l'expression régulière. En fait, je pense que le problème est dans NP (voir le commentaire ci-dessous la réponse de FrankW.)
Raphael

Réponses:

11

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)kVVkEV

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 .01(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, ou1

  • 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:

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

VUNE=0|10110

VB=0|11101

VC=0|10011

V=0|11000

Counter=0|010|01010

E1=01(0|1)

E2=01(0|1)

E3=01(0|1)

E4=01(0|1)

VUNEVCounterE1E4

VUNE,VBVC,VB

Counter0|0dix

FrankW
la source
2
Puisque nous pouvons a) calculer NFA de taille polynomiale pour les expressions régulières ainsi que deviner b) la solution et c) les calculs (de taille linéaire) de tous les NFA et d) vérifier (en temps polynomial) que les calculs correspondent aux mots devinés, le problème est également dans NP.
Raphael
2

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

Steve
la source