O regex golf NP-Complete?

27

Como visto nesta faixa recente do XKCD e nesta postagem recente no blogde Peter Norvig (e uma história do Slashdot com o último), "regex golf" (que pode ser chamado de problema de separação de expressões regulares) é o quebra-cabeça de definir a expressão regular mais curta possível que aceita todas as palavras do conjunto A e nenhuma palavra no conjunto. o post do conjunto B. Norvig inclui um algoritmo para gerar um candidato razoavelmente curto, e ele observa que sua abordagem envolve a solução de um problema NP-Set Set Cover, mas também é cuidadoso em ressaltar que sua abordagem não considera todas as expressões regulares possíveis, e, é claro, ele não é necessariamente o único algoritmo; portanto, não é garantido que suas soluções sejam ótimas, e também é possível que algum outro algoritmo de tempo polinomial com certeza possa encontrar soluções equivalentes ou melhores.

Por uma questão de concretude e para evitar ter que resolver a questão da otimização, acho que a formulação mais natural da Separação por Expressão Regular seria:

Dado dois conjuntos (finitos) e B de strings sobre algum alfabeto Σ , existe uma expressão regular de comprimento k que aceita todas as strings de A e rejeita todas as strings de B ?ABΣkAB

Sabe-se alguma coisa sobre a complexidade desse problema específico de separação? (Observe que desde que eu especifiquei e B como conjuntos finitos de cadeias, a noção natural de tamanho para o problema é o comprimento total de todas as cadeias em A e B ; isso substitui qualquer contribuição de k ). Parece-me altamente provável que seja NP-completo (e, de fato, eu esperaria que a redução fosse para algum tipo de problema de cobertura), mas algumas pesquisas não revelaram nada particularmente útil.ABABk

Steven Stadnicki
fonte
4
É mesmo em NP? Dada uma expressão regular, como você verifica se uma palavra está no idioma descrito no tempo polinomial? A abordagem padrão - transformar em NFA, depois DFA e verificação - leva tempo exponencial em (?). k
Raphael
11
deve ser completo no PSPACE; ver (Gramlich, Schnitger, minimizando NFAs e Expressões Regulares, 2005) em ggramlich.github.io/Publications/approximationSTACS05Pres.pdf e citeseerx.ist.psu.edu/viewdoc/... (PS: Eu estou postando isso como um comentário, porque uma resposta deve explicar por que, mas eu não tenho tempo para fazê-lo no momento, talvez alguém pode usar a referência e explicar como ele funciona)
rgrig
11
Para expressões regulares, como entendido no TCS, o problema está no NP (um certificado de tamanho polinomial e verificável em tempo polinomial seria a própria expressão regular). (Provavelmente) não está no NP se usarmos, por exemplo, PCREs para expressões regulares, porque até o teste de associação é difícil para NP ( perl.plover.com/NPC/NPC-3SAT.html ).
Mike B.
11
@ MikeB .: E como exatamente você verifica o tempo polinomial? Você viu o comentário de @Raphael?
rgrig
5
(1) Você pode executar um algoritmo determinístico em P para testar a associação de NFAs (comece no estado inicial e lembre-se de todos os estados em que pode estar depois de consumir um símbolo da palavra. Chegue ao fim, verifique se alcançou pelo menos um estado final.) (2) Depende da definição de "expressão regular" - usamos o de cientistas da computação ou o de programadores? Permitimos apenas linguagens regulares ou (um subconjunto de) linguagens sensíveis ao contexto (daí PCREs)?
Mike B.

Respostas:

15

Assumindo a variante TCS do regex, o problema é realmente NP-complete.

Assumimos que nossas expressões regulares contêm

  • cartas de , combinando-se,Σ
  • , denotando união,+
  • , denotando concatenação,
  • , denotando Kleene-Star,
  • , correspondendo à sequência vaziaλ

e nada mais. O comprimento de uma regex é definido como o número de caracteres de . Como na história em quadrinhos, consideramos um regex para corresponder a uma palavra, se corresponder a uma substring da palavra. (Alterar qualquer uma dessas suposições deve influenciar apenas a complexidade da construção abaixo, mas não o resultado geral.)Σ

AB

Para mostrar a dureza NP, reduzimos a tampa do conjunto:

UCUCCkSCS=U

Traduzimos uma entrada para Set cover em uma para regex golf da seguinte maneira:

  • ΣCx
  • AeUCe
  • Bx
  • k

Essa redução está obviamente em P e a equivalência também é bastante simples de ver:

  • c1,,ckc1++ck
  • xAkΣAC
FrankW
fonte
11
ABO(n)a1+a2+...,aiAO(n)k
2
AB