¿Son los crucigramas regex NP-hard?

13

Estaba jugando el otro día en este sitio web: http://regexcrossword.com/ y me pregunté cuál era la mejor manera de resolverlo.

¿Puedes resolver el siguiente problema en tiempo polinómico o es NP-hard?

Dada una cuadrícula NxM con N expresiones regulares para las columnas y M para las filas, encuentre cualquier solución a la cuadrícula de modo que se satisfagan todas las expresiones regulares, o diga que no existe una solución.

Glen Takahashi
fuente
Todavía no he visto el sitio, pero las preguntas con Regexes tienden a ser PSPACE completas, una clase que es al menos tan difícil como NP
jmite
1
@jmite Adivinar cadenas que se ajustan a algunas expresiones regulares es "fácil" ya que no tenemos que derivar alguna propiedad global de la expresión regular. De hecho, creo que el problema está en NP (ver comentario debajo de la respuesta de FrankW)
Raphael

Respuestas:

11

El problema es NP-hard.

Mostramos esto reduciendo la cubierta del vértice:

Dado un gráfico y un umbral k , ¿hay un subconjunto V V de cardinalidad como máximo k , de modo que cada borde en E incide en al menos un nodo en V ?sol=(V,mi)kVVkmiV

Traducimos esto en un crucigrama regex con columnas y | V | filas de la siguiente manera:El |miEl |+1El |VEl |

Todas las columnas, excepto la primera, corresponden a un borde. Obtienen una expresión regular .0 01(0 0El |1)

Todas las filas corresponden a un vértice. Obtienen una expresión regular que les permite escribir

  • un en la primera columna y cada columna correspondiente a un borde incidente a ese nodo y ceros en todas las otras columnas, o1

  • 0 0

Finalmente, la primera columna cuenta el tamaño de la cubierta del vértice. Obtiene una expresión regular, que permite a lo sumo más.k

La correspondencia entre las soluciones al crucigrama regex y las cubiertas de vértice debería ser obvia.

Ejemplo:

Encuentre una cubierta de vértice de tamaño 2 para el siguiente gráfico:

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

VUN=0 0El |10110

Vsi=0 0El |11101

VC=0 0El |10011

Vre=0 0El |11000

Cotunortetmir=0 0El |0 010El |0 01010

mi1=0 01(0 0El |1)

mi2=0 01(0 0El |1)

mi3=0 01(0 0El |1)

mi4 4=0 01(0 0El |1)

VUNVreCotunortetmirmi1mi4 4

VUN,VsiVC,Vsi

Cotunortetmir0 0El |0 010

FrankW
fuente
2
Como podemos a) calcular NFA de tamaño polinómico para las expresiones regulares, así como adivinar b) la solución yc) cálculos (de tamaño lineal) de todos los NFA yd) verificar (en tiempo polinómico) que los cálculos se ajustan a las palabras adivinadas, El problema también está en NP.
Raphael