Um oráculo para separar NP de coNP

Como provar que ? Estou apenas procurando por um oracle TM M e uma linguagem recursiva L ( M ) = L para a qual isso se aplica.$\mathsf{NP}^A \neq \mathsf{coNP}^A$$M$$L(M) = L$

Eu sei que a prova de que você mostra que há um oráculo tal que P A ≠ N P A e um oráculo A tal que P A = N P A . Tenho uma dica de que devo encontrar esse oráculo A estendendo a prova de P A ≠ N P A, mas sempre que procuro e leio, é "óbvio" ou "direto" em todos os lugares, mas simplesmente não vejo como provar isso. .$A$$\mathsf{P}^A \neq \mathsf{NP}^A$$A$$\mathsf{P}^A = \mathsf{NP}^A$$A$$\mathsf{P}^A \neq \mathsf{NP}^A$

Como Max disse que a modificação não é difícil, eu sugiro que você não ler o resto desta resposta e pensar sobre o problema um pouco mais, só há uma parte que precisa de modificação e lembrando a definição de quando um A máquina aceita ajudará você a consertar essa parte.$\mathsf{coNP}$

Vou explicar a modificação necessária abaixo, mas primeiro vamos ter uma breve visão na prova original.

Na prova original é construído em etapas, onde na etapa i com o make certeza que i th máquina em P , M i , não decide a linguagem { x | ∃ y ∈ A | x | = | y | } corretamente. Note-se que o conjunto é em N P A .$A=\bigcup_n A_n$$i$$i$$\mathsf{P}$$M_i$$\{x \mid \exists y\in A \ |x|=|y| \}$$\mathsf{NP}^A$

Conseguimos isso simulando usando a parte de A que construímos em 0 m, em que m é grande o suficiente (a string é mais longa do que as consideradas nas etapas anteriores). M i aceita, não adicionamos nada; se ele rejeita, adicionamos uma cadeia de comprimento m que M i não faz uma consulta ao conjunto (essa cadeia existe, pois existem exponencialmente muitas cadeias de comprimento m, mas M i não pode perguntar sobre todos eles em tempo polinomial). Não modificaremos esta parte de A em etapas futuras (ou seja, cadeias de comprimento $M_i$$A$$0^m$$m$$M_i$$m$$M_i$$m$$M_i$$A$$m$ou menos permanecerá o mesmo). Isso garante que não decida o idioma corretamente e complete a prova.$M_i^A$

Agora, assume que as máquinas foram em c O N P em lugar de P . Precisamos modificar a prova para se certificar de que M Um i não reconhecerá L . Se estiver aceitando, mantemos A como antes e tudo funciona bem como na prova original. Se rejeitar, precisamos adicionar uma sequência ao conjunto para garantir que ela não responda corretamente. Ainda podemos simular M i com a parte de A que temos, o problema é que M i pode consultar todas as cadeias de comprimento n . Aqui a forma como um c $M_i$$\mathsf{coNP}$$\mathsf{P}$$M_i^A$$L$$A$$M_i$$A$$M_i$$n$$\mathsf{coNP}$ funcionamento da máquina se torna importante. Ele aceita se e somente se todos os caminhos de computação aceitarem. Como está rejeitando neste caso, há um caminho de computação que está rejeitando. Enquanto mantivermos esse caminho intacto, tudo funcionará; portanto, precisamos manter as respostas para as consultas nesse caminho iguais. O número de consultas nesse caminho é polinomial (já que a máquina é executada em tempo polinomial), portanto, existem cadeias de comprimento que o caminho não consulta, basta adicionar uma delas a A e o restante da prova funciona como antes.$m$$A$

Os passos são algorítmicos, portanto, o conjunto é recursivo (a parte essencial da construção é a capacidade de simular máquinas, o que pode ser feito, por exemplo, D S p a c e ( n ω ( 1 )$A$$\mathsf{DSpace}(n^{\omega(1)})$ ).

Você também pode consultar o texto Complexidade Computacional de Christos Papadimitriou. Especificamente, o Capítulo 14, Seção 3, que investiga os oráculos. Provas para$P^A = NP^A$ e $P^B \not= NP^B$ para alguns oráculos $A$ e $B$por exemplo, são fornecidos em detalhes e podem ser úteis para o seu problema principal. Espero que ajude.