Como se ve en esta reciente tira de XKCD y esta reciente publicación de blogde Peter Norvig (y una historia de Slashdot con este último), "regex golf" (que podría llamarse el problema de separación de expresiones regulares) es el rompecabezas de definir la expresión regular más corta posible que acepte cada palabra en el conjunto A y ninguna palabra en la publicación del conjunto B. Norvig incluye un algoritmo para generar un candidato razonablemente corto, y señala que su enfoque implica resolver un problema de cubierta de conjunto completa de NP, pero también tiene cuidado de señalar que su enfoque no considera todas las expresiones regulares posibles, y, por supuesto, el suyo no es necesariamente el único algoritmo, por lo que no se garantiza que sus soluciones sean óptimas, y también es posible que algún otro algoritmo de tiempo polinomial pueda encontrar soluciones equivalentes o mejores.
En aras de la concreción y para evitar tener que resolver la cuestión de la optimización, creo que la formulación más natural de la separación de expresiones regulares sería:
Dados dos conjuntos (finitos) y de cadenas sobre algún alfabeto , ¿existe una expresión regular de longitud que acepte cada cadena en y rechace cada cadena en ?B Σ ≤ k A B
¿Se sabe algo sobre la complejidad de este problema particular de separación? (Tenga en cuenta que dado que he especificado y como conjuntos finitos de cadenas, la noción natural de tamaño para el problema es la longitud total de todas las cadenas en y ; esto empantana cualquier contribución de ). Me parece muy probable que sea NP completo (y, de hecho, esperaría que la reducción se deba a algún tipo de problema de cobertura), pero algunas búsquedas no han resultado nada particularmente útil.A B k
fuente
Respuestas:
Suponiendo la variante TCS de regex, el problema es de hecho NP-completo.
Asumimos que nuestras expresiones regulares contienen
y nada más. La longitud de una expresión regular se define como el número de caracteres de . Como en la tira cómica, consideramos una expresión regular para que coincida con una palabra, si coincide con una subcadena de la palabra. (Cambiar cualquiera de estos supuestos solo debería influir en la complejidad de la construcción a continuación, pero no en el resultado general).Σ
Que esté en NP es sencillo, como se explica en los comentarios (verifique un candidato-RE traduciéndolo a un NFA y ejecutándolo en todas las palabras de y ).BA B
Para mostrar la dureza NP, reducimos la cobertura del conjunto:
Traducimos una entrada para Set cover en una para regex golf de la siguiente manera:
Esta reducción es obviamente en P y la equivalencia también es bastante simple de ver:
fuente