Como entender co-$\mathcal{L}$ onde $\mathcal{L}$ é uma classe de linguagens

Question

Acho que este é um tópico básico em complexidade, mas gostaria de perguntar como entender co-$\mathcal{L}$ onde $\mathcal{L}$ é uma classe de línguas.Pela definição do meu livro, $$co-\mathcal{L} = \{ \overline{L} \mid L \in \mathcal{L} \}$$

e onde $\overline{L}$ é o complemento.Pelo que li numa parte anterior do meu livro, o complemento de $L$ é igual a $\Sigma^* - L$.

No entanto, diga que $\mathcal{L}$ é NP.Uma instância de uma linguagem $L$ Que está em $\mathcal{L}$ é o conjunto de gráficos com caminhos hamiltonianos.Porém, neste caso, seu complemento $\bar{L} \in$co-$\mathcal{L}$ é o conjunto de gráficos sem caminhos hamiltonianos, ou seja, $bar{L} em $co-NP.

Mas o conjunto de gráficos sem caminhos hamiltonianos é igual a $\Sigma^* - L$ (seguindo a definição de complemento)?Neste caso, estaríamos incluindo algumas strings $\in\Sigma^* - L$ que não representam gráficos.

Outro exemplo é $A_{TM}$, que representa o idioma

$$\{\langle M,w angle \mid M ext{ aceita entrada } w \}$$

Neste caso, faz $\overline{A_{TM}}$ representar $\Sigma^* -A_{TM}$?.Se for esse o caso, estaríamos incluindo $\overline{A_{TM}}$ várias strings que não representam TMs, ou que se referem a outra entrada que não é igual a $w$.Ou melhor, faz $\overline{A_{TM}}$ representa a língua

$$\{\langle M,w angle \mid M ext{ diverge na entrada } w \}$$

Answer 1

Normalmente pensamos nas instâncias dos problemas como estando em algum formato.Existem várias maneiras de pensar nisso.Considere por exemplo $A_{TM}$, em que a entrada é um par $\langle M,w angle$.Os três mais óbvios são:

1. Cada string de entrada pode ser decodificada em um par de entrada $\langle M,w angle$.
2. Entradas não do formulário $\langle M,w angle$ não pertencem à língua.
3. Nós pensamos em $A_{TM}$ como um problema de promessa:entradas $\langle M,w angle$ onde $M$ aceita $w$ são instâncias Sim, entradas $\langle M,w angle$ onde $M$ não aceita $w$ não há instâncias e não nos importamos com outras entradas.

Se você aceitar a complementação, aqui está o que você obtém em cada interpretação:

1. $\overline{A_{TM}}$ consiste em todas as strings de entrada que, quando decodificadas para $\langle M,w angle$, são tais que $M$ não aceita $w$.
2. $\overline{A_{TM}}$ consiste em entradas que não são da forma $\langle M,w angle$, e daqueles da forma $\langle M,w angle$ de tal modo que $M$ não aceita $w$.
3. $\overline{A_{TM}}$ é o problema da promessa correspondente à opção 1.

Embora essas diferentes interpretações pareçam diferentes, na prática a diferença é muito pequena, visto que é fácil reconhecer que a entrada está no formato correto.Por exemplo, dada a interpretação 2, considere os dois idiomas a seguir: $\overline{A_{TM}}$, e $\widetilde{A_{TM}}$, a linguagem de todos os pares $\langle M,w angle$ de tal modo que $M$ não aceita $w$.Essas duas linguagens diferem em entradas malformadas, ou seja, saídas que não estão no formato $\langle M,w angle$.Como tais entradas são fáceis de detectar, temos um algoritmo para $\overline{A_{TM}}$ se tivermos um para $\widetilde{A_{TM}}$, e, além disso, a complexidade de ambos os algoritmos é muito semelhante.

Por esta razão, normalmente ignoramos tais questões e trabalhamos implicitamente sob a interpretação do “problema da promessa”:a entrada é assumida como sendo da forma $\langle M,w angle$.Os puristas podem pensar na primeira interpretação, que deste ponto de vista se comporta de forma idêntica.

De forma mais geral, seja qual for a interpretação que você escolher, você ainda terá que descrever formalmente para que codificação é usada $\langle M,w angle$.Normalmente não nos preocupamos, uma vez que todas as interpretações razoáveis ​​são interredutíveis e, portanto, não alteram a computabilidade ou a complexidade do problema.Dito isto, a diferença entre dureza NP fraca e dureza NP forte reside exatamente em qual representação de entrada está sendo usada.