Qual é a complexidade do problema da universalidade para uma NFA com todos os estados aceitando?

É sabido que o problema da universalidade para a NFA (decidir se $L(A)=\Sigma^*$ ) é $PSPACE$ -completo. No entanto, e se todos os estados da NFA estiverem aceitando? Parece-me que o problema está no máximo $co$ - $NP$ , como um contra-exemplo (diferente do caso de uma NFA geral) é polinomial (mesmo linear) no tamanho da entrada (o número de estados). Qual é a complexidade desse problema?

complexity-theory regular-languages finite-automata pron
fonte

A menos que haja um problema na minha prova, é muito improvável que o seu problema seja co-NP, porque isso implicaria que co-NP = PSPACE. Como um contraexemplo (ou seja, uma palavra rejeitada) poderia realmente ser verificado no tempo polinomial em seu tamanho, eu seria tentado a dizer que deve haver um problema em sua prova de que sempre existe um contraexemplo de tamanho polinomial. Você poderia explicar como encontraria um contra-exemplo de tamanho polinomial? A única coisa que eu conseguia pensar era em busca de um caminho mais curto para um estado em que a função de transição não é total, mas pode haver outro caminho que obras ...

xavierm02

Não é verdade que o menor contra-exemplo tenha tamanho polinomial. Considere um NFA cujo estado inicial esteja conectado a ciclos de comprimentos

2, p_{1}, \dots, p_{m}

$2,p_1,\ldots,p_m$ . Você pode organizar a palavra

1^{n} 0

$1^n0$ não deve ser aceito somente se

n

$n$ é ímpar e um múltiplo de

p_{1}, \dots, p_{m}

$p_1,\ldots,p_m$ . Escolhendo o

p_{i}

$p_i$ ser o primeiro

m + 1

$m+1$ primos, você obtém um NFA com

O (m^{2} \log m)

$O(m^2\log m)$ estados em que a menor palavra rejeitada tem tamanho

e^{(1 + o (1)) m \log m}

$e^{(1+o(1))m\log m}$ .

Yuval Filmus

Uma simples redução do SAT mostra que o problema é realmente difícil de coNP. A NFA se divide em partes de acordo com as cláusulas. Cada parte verifica se a entrada, que consiste em uma atribuição seguida de

$

$\$$ , satisfaz a cláusula e, se assim for, fica preso na final

$

$\$$ . Esse NFA não é universal se a instância do SAT for satisfatória.

Yuval Filmus

@YuvalFilmus Você está correto em relação ao contra-exemplo, mas, como se vê, eu deturpou o problema. Eu sei disso

L (A)

$L(A)$ não possui palavras com letras repetidas consecutivas e estou procurando universalidade com relação a todas as palavras sem letras repetidas consecutivas. Também existe um contra-exemplo exponencial nesse caso?

pron

@YuvalFilmus Além disso, o alfabeto não é maior que o número de estados + 1.

pron 10/17

Respostas:

Seu problema está completo no PSPACE. Eu provo que é difícil para o PSPACE, reduzindo a universalidade das NFAs à universalidade das NFAs, com todos os estados aceitando.

Deixei $A$ ser um NFA. Adicionar um novo estado final $q_\$$ para ele e para todos os estados que aceitam $q$ , adicione uma transição $q\overset{\$}{\to}q_\$$ Onde $\$$ é uma nova carta. Para cada letra $a\in \Sigma\sqcup \{\$\}$ , também adicione uma transição $q_\$\overset{a}{\to}q_\$$ . E então faça todos os estados aceitarem. O novo autômato aceita $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup L'$ para alguns $L'\subseteq \Sigma^*$ .

Agora, adicione algum autômato (com todos os estados finais) que reconheça o idioma $\Sigma ^*$ (ou seja, o idioma das palavras que não contêm $\$$ ) em paralelo. O novo autômato reconhecerá $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup (L' \cup \Sigma ^*)=L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*$ .

Agora, observe que temos $L(A)=\Sigma^*$ iff $L(A)\$ (\Sigma\sqcup \{\$\})^* \sqcup \Sigma ^*=(\Sigma\sqcup\{\$\})^*$ . Ou seja, o processo que descrevi é uma redução da universalidade de uma NFA para a universalidade de uma NFA, com todos os estados aceitando. Como a redução é polinomial, seu problema é difícil com o PSPACE.

xavierm02
fonte

Como você constrói um NFA para

Σ^{*} ∖ Σ^{*} $

$\Sigma^* \setminus \Sigma^*\$$ todos os estados de quem estão aceitando?

Yuval Filmus

Obrigado, é uma boa redução e, de fato, responde à minha pergunta. No entanto, eu tinha uma pergunta diferente e mais complexa em mente, que pensei que poderia reduzir a essa, e o contra-exemplo exponencial da @YuvalFilmus me fez perceber que minha própria redução estava com defeito, e eu deveria ter acrescentado a restrição de que

L (A)

$L(A)$ não contém palavras com letras repetidas e estou verificando a "universalidade" em relação a essas palavras.

pron

@pron O que você quer dizer com "palavra com letras repetidas"? que

u = v_{1} a a v_{2}

$u=v_1aav_2$ ou aquilo

u = v_{1} a v_{2} a v_{3}

$u=v_1av_2av_3$ ?

Xmlm02

@ xavierm02 O primeiro, ou seja, sem letras repetidas consecutivas . Também existe um contra-exemplo exponencial nesse caso?

pron

@ xavierm02 Além disso, o alfabeto não é maior que o número de estados + 1.

pron