As palavras cruzadas regex são NP-difíceis?

13

Eu estava brincando no outro dia neste site: http://regexcrossword.com/ e isso me fez pensar em qual seria a melhor maneira de resolvê-lo.

Você pode resolver o seguinte problema em tempo polinomial ou é NP-difícil?

Dada uma grade NxM com N expressões regulares para as colunas e M para as linhas, encontre qualquer solução para a grade, de modo que todas as expressões regulares sejam satisfeitas, ou diga que não existe solução.

Glen Takahashi
fonte
Ainda não consultamos o site, mas as perguntas com Regexes tendem a ser completas para o PSPACE, uma classe que é pelo menos tão difícil quanto a NP
jmite
1
@jmite Adivinhar strings que se encaixam em algumas expressões regulares é "fácil", pois não precisamos derivar alguma propriedade global da expressão regular. Na verdade, acho que o problema está no NP (veja o comentário abaixo da resposta de FrankW).
Raphael

Respostas:

11

O problema é NP-difícil.

Mostramos isso reduzindo a cobertura de vértices:

Dado um gráfico e um limiar k , existe um subconjunto V V de cardinalidade no máximo k , de modo que cada aresta em E incida em pelo menos um nó emG=(V,E)kVVkE ?V

Nós traduzimos isso em palavras cruzadas regex com coluna e|E|+1linhas da seguinte maneira:|V|

Todas as colunas, exceto a primeira, correspondem a uma aresta. Eles recebem um regex .0 01(0 0|1)

Todas as linhas correspondem a um vértice. Eles recebem um regex que permite escrever

  • um na primeira coluna e cada coluna correspondente a um incidente de borda nesse nó e zera em todas as outras colunas, ou1

  • 0 0

Finalmente, a primeira coluna conta o tamanho da capa do vértice. Obtém um regex, que permite no máximo .k

A correspondência entre soluções para as palavras cruzadas regex e capas de vértice deve ser óbvia.

Exemplo:

Encontre uma cobertura de vértice de tamanho 2 para o seguinte gráfico:

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

VUMA=0 0|10110

VB=0 0|11101

VC=0 0|10011

VD=0 0|11000

Covocênter=0 0|0 010|0 01010

E1=0 01(0 0|1)

E2=0 01(0 0|1)

E3=0 01(0 0|1)

E4=0 01(0 0|1)

VUMAVDCovocênterE1E4

VUMA,VBVC,VB

Covocênter0 0|0 010

FrankW
fonte
2
Como podemos a) computar NFA de tamanho polinomial para as expressões regulares e adivinhar b) a solução ec) (cálculos de tamanho linear) de todos os NFA ed) verificar (em tempo polinomial) se os cálculos se encaixam nas palavras adivinhadas, o problema também está no NP.
Raphael
2

A questão permanece NP-completa, mesmo quando todas as expressões regulares são iguais. http://arxiv.org/abs/1411.5437

Steve
fonte