A relativização está bem definida?

8

De acordo com o teorema BGS [1], existe um oráculo tal que P UmN P A .APANPA

Se a operação de relativização fosse uma função bem definida, seria de esperar que, a partir de B AC A, seria possível concluir que B C , por exemplo, P N P seguiria o BGS. No entanto, P N P ainda está aberto.BBABACABCPNPPNP

Isso significa que a relativização não é uma função bem definida?

Em caso afirmativo, temos algum exemplo de duas relativizações comprovadamente diferentes da mesma classe de complexidade?

[1] TP Baker, J. Gill e R. Solovay, "Relativizações da questão P =? NP"

Michael
fonte
3
Baker-Gill-Solovay mostra dois oráculos: um onde P e NP são iguais e outro onde não são. Isso responde à sua última pergunta.
Suresh Venkat
A,BPANPAPB=NPBPB=NPBP=NPPANPAPNP
2
@Kaveh seria útil para apontar para respostas específicas. Eu fiz uma varredura rápida das perguntas e não vi nada.
Suresh Venkat
2
PS: a resposta curta para sua pergunta é que uma relativização não é um operador extensional / funcional na classe de problemas, mesmo que a notação pareça implicar em contrário. Não existe uma definição geral de relativização para classes de problemas, as relativizações são definidas para modelos de máquinas e um único modelo de máquina pode ter várias versões relativizadas diferentes.
Kaveh
1
fyi fortnow notas / admite em seus abstrato que teóricos da complexidade tanto para uso e "mau uso" relativização .... parece ser uma área reconhecidamente cinza da teoria da complexidade , às vezes ....
vzn

Respostas:

13

BBA

Pense P Uma como sendo uma espécie de generalização de P, que é igual a P, quando A está vazio, mas por outro lado pode ser diferente. Agora, se você só sabe o conjunto P, não está claro como generalizar isso para obter P A . Como analogia, se eu pedisse para você generalizar os números reais, não está claro que generalização estou procurando. Estou pensando em campos, anéis, espaços vetoriais etc.? A razão para isso é que, enquanto P é meramente um conjunto de linguagens, P A é definido em termos de uma máquina. Esta máquina possui a propriedade de que, quando A estiver vazio, ele decida exatamente os mesmos idiomas que P. Você poderá criar outra máquina, vamos chamá-lo de Q A , que também possui a propriedade de que, quando A estiver vazio, decidir os mesmos idiomas que P Isso não significa que PA = Q A para todos A. Isso seria análogo a afirmar que, se f (0) = g (0), então feg são a mesma função.

Talvez este post de Terence Tao seja útil.

Robin Kothari
fonte
Obrigado, Robin. Essa é outra boa resposta, e o link para o artigo de Tao é muito útil.
Suresh Venkat
4

(Suponho que essa pergunta acabe sendo migrada para o CS.SE, mas estou postando minha resposta aqui no cstheory por enquanto.)

Tecnicamente, não se costuma pensar na relativização como um "operador" ou "função"; no entanto, não vejo uma razão pela qual você não possa tomar uma declaração e mapeá-la para uma versão relativizada dela.

O truque é que, como outros já disseram, a relativização não é realmente definida sobre uma classe de complexidade; em vez disso, é definido no modelo de computação que você está usando. Além disso, o que relativiza é a afirmação, não as classes. (A notação é um pouco enganadora.)

Um exemplo disso é que eu poderia dizer teoricamente que uma afirmação relativiza (ou, menos provavelmente, não relativiza), mesmo que não se refira a uma máquina de Turing. Por exemplo, eu poderia dizer (sinceramente), "1 + 1 = 2" relativiza, porque em relação a todos os oráculos que poderiam ser adicionados à definição da minha máquina de Turing universal, 1 + 1 = 2 permaneceria verdadeiro.

Portanto, a resposta curta é: Sim, é bem definido, mas não nas aulas.

Philip White
fonte
1
PANPAP=NPA
2
Era isso que eu estava recebendo na minha resposta ... Eu disse, você não pode relativizar ao longo das aulas, você relativiza ao longo das declarações. A capacidade de relativizar sobre P e NP desaparece se você não puder relativizar sobre classes individualmente; o argumento não funciona se eu apenas disser "relativizei uma declaração, agora inverta a relativização e ela ainda deve conter" mais do que é possível dizer (usando a função f (x) = x ^ 2 como exemplo) " 5 ^ 2 é composto "->" 5 é composto ".
Philip White
2
Não existe uma definição geral de relativização de declarações. Existem apenas modelos relativizados de computação. A relativização de P vs. NP pressupõe que fixamos os modelos relativizados de P e NP de antemão.
Kaveh