Um oráculo para separar NP de coNP

12

Como provar que ? Estou apenas procurando por um oracle TM M e uma linguagem recursiva L ( M ) = L para a qual isso se aplica.NPAcoNPAML(M)=L

Eu sei que a prova de que você mostra que há um oráculo tal que P AN 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 AN P A, mas sempre que procuro e leio, é "óbvio" ou "direto" em todos os lugares, mas simplesmente não vejo como provar isso. .APANPAAPA=NPAAPANPA

Stewenson
fonte
6
Não está claro se você seguiu a dica. Surpreende-me ao saber que é óbvio, mas você pode encontrar a prova em (por exemplo) Complexidade Computacional: Uma Abordagem Moderna de Arora e Barak. PANPA

Respostas:

9

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.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=nAniiPMi{xyA |x|=|y|}NPA

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 mMiA0mmMimMimMiAmou menos permanecerá o mesmo). Isso garante que não decida o idioma corretamente e complete a prova.MiA

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 oMicoNPPMiALAMiAMincoNP 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.mA

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 ) )ADSpace(nω(1)) ).

Kaveh
fonte
3

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 paraPUMA=NPUMA e PBNPB para alguns oráculos UMA e Bpor exemplo, são fornecidos em detalhes e podem ser úteis para o seu problema principal. Espero que ajude.

Vincent Russo
fonte