Le regex golf est-il NP-Complete?

27

Comme on le voit dans cette récente bande XKCD et ce récent article de blogde Peter Norvig (et une histoire de Slashdot mettant en vedette ce dernier), "regex golf" (qui pourrait mieux être appelé le problème de séparation des expressions régulières) est le casse-tête de définir l'expression régulière la plus courte possible qui accepte chaque mot de l'ensemble A et aucun mot de le poste de B. Norvig comprend un algorithme pour générer un candidat raisonnablement court, et il note que son approche consiste à résoudre un problème de NP Set complet, mais il prend également soin de souligner que son approche ne prend pas en compte toutes les expressions régulières possibles, et bien sûr, ce n'est pas nécessairement le seul algorithme, donc ses solutions ne sont pas garanties d'être optimales, et il est également possible qu'un autre algorithme à temps polynomial assurément puisse trouver des solutions équivalentes ou meilleures.

Pour le concret et pour éviter d'avoir à résoudre la question d'optimisation, je pense que la formulation la plus naturelle de la séparation des expressions régulières serait:

Étant donné deux ensembles (finis) et de chaînes sur un alphabet , existe-t-il une expression régulière de longueur qui accepte chaque chaîne de et rejette chaque chaîne de ?B Σ k A BABΣkAB

Connaît-on la complexité de ce problème de séparation particulier? (Notez que puisque j'ai spécifié et comme ensembles finis de chaînes, la notion naturelle de taille pour le problème est la longueur totale de toutes les chaînes en et ; cela submerge toute contribution de ). Il me semble très probable qu'il est NP-complet (et en fait, je m'attendrais à ce que la réduction soit à une sorte de problème de couverture), mais quelques recherches n'ont rien trouvé de particulièrement utile.B A B kABABk

Steven Stadnicki
la source
4
Est-ce même en NP? Étant donné une expression régulière, comment vérifiez-vous si un mot est dans la langue décrite en temps polynomial? L'approche standard - transformer en NFA, puis DFA et vérifier - prend un temps exponentiel en (?). k
Raphael
1
devrait être PSPACE-complet; voir (Gramlich, Schnitger, Minimizing NFAs and Regular Expressions, 2005) sur ggramlich.github.io/Publications/approximationSTACS05Pres.pdf et citeseerx.ist.psu.edu/viewdoc/… (PS: je poste ceci en tant que commentaire, parce qu'une réponse devrait expliquer pourquoi, mais je n'ai pas le temps de le faire pour le moment; peut-être que quelqu'un d'autre peut utiliser la référence et expliquer comment cela fonctionne)
rgrig
1
Pour les expressions régulières telles que comprises dans TCS, le problème est dans NP (Un certificat de taille polynomiale et vérifiable en temps polynomial serait l'expression régulière elle-même). Il n'est (probablement) pas dans NP si nous utilisons par exemple des PCRE pour les expressions régulières, car même le test d'adhésion est NP-difficile ( perl.plover.com/NPC/NPC-3SAT.html ).
Mike B.
1
@MikeB .: Et comment vérifiez-vous exactement le temps polynomial? Avez-vous vu le commentaire de @Raphael?
rgrig
5
(1) Vous pouvez exécuter un algorithme déterministe en P pour tester l'appartenance aux NFA (commencez à l'état de début, et rappelez-vous tous les états dans lesquels vous pouvez être après avoir consommé un symbole du mot. Atteignez la fin, vérifiez si vous avez atteint au moins un état final.) (2) Cela dépend de la définition de l'expression régulière - utilisons-nous celle des informaticiens ou celle des programmeurs? Autorisons-nous uniquement les langues régulières ou (un sous-ensemble de) langues sensibles au contexte (d'où les PCRE)?
Mike B.

Réponses:

15

En supposant la variante TCS de l'expression régulière, le problème est en effet NP-complet.

Nous supposons que nos regex contiennent

  • lettres de , se faisant correspondre,Σ
  • + , désignant l'union,
  • , indiquant la concaténation,
  • , désignant Kleene-Star,
  • λ , correspondant à la chaîne vide

et rien d'autre. La longueur d'une expression régulière est définie comme le nombre de caractères de . Comme dans la bande dessinée, nous considérons une expression régulière pour correspondre à un mot, si elle correspond à une sous-chaîne du mot. (La modification de l'une de ces hypothèses ne devrait influer que sur la complexité de la construction ci-dessous, mais pas sur le résultat général.)Σ

Le fait qu'il soit en NP est simple, comme expliqué dans les commentaires (vérifiez un candidat-RE en le traduisant en NFA et en l'exécutant sur tous les mots de et ).BAB

Afin de montrer la dureté NP, nous réduisons la couverture Set:

Étant donné un univers et une collection de sous-ensembles de , existe-t-il un ensemble de taille sorte que ?C U C C k S C S = UUCUCCkSCS=U

Nous traduisons une entrée pour Set cover en une pour regex golf comme suit:

  • C xΣ contient un caractère pour chaque sous-ensemble en et un caractère supplémentaire (noté dans la suite).Cx
  • e U C eA contient un mot pour chaque élément d' . Le mot se compose exactement des caractères représentant les sous-ensembles en qui contiennent (dans un ordre arbitraire).eUCe
  • xB contient le seul mot .x
  • k est simplement reporté.

Cette réduction est évidemment en P et l'équivalence est également assez simple à voir:

  • Si est une solution pour l'instance de couverture définie, l'expression est une solution pour regex golf.c 1 + + c kc1,,ckc1++ck
  • Une expression régulière correspondant au sous-mot vide correspondrait à . Ainsi, toute regex résoudre le problème de golf doit contenir au moins une lettre de chacun des mots . Par conséquent, si l'instance de golf est résoluble, il existe un ensemble d'au plus lettres de sorte que chaque mot de est couvert par cet ensemble de lettres. Par construction, l'ensemble correspondant de sous-ensembles de est une solution à l'instance de couverture d'ensemble.A k Σ A CxAkΣAC
FrankW
la source
1
ABO(n)a1+a2+...,aiAO(n)k
2
AB