A relativização está bem definida?

De acordo com o teorema BGS [1], existe um oráculo tal que . $A$ $P^A\neq NP^A$

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

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"

cc.complexity-theory oracles relativization Michael
fonte

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, B

$A,B$

P^{A} \neq N P^{A}

$P^A\neq NP^A$

P^{B} = N P^{B}

$P^B=NP^B$

P^{B} = N P^{B}

$P^B=NP^B$

P = N P

$P=NP$

P^{A} \neq N P^{A}

$P^A\neq NP^A$

P \neq N P

$P\neq NP$

@Kaveh seria útil para apontar para respostas específicas. Eu fiz uma varredura rápida das perguntas e não vi nada.

Suresh Venkat

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

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:

$B\mapsto B^A$

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 P^A = 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

(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

P^{A} \neq N P^{A}

$P^A \ne NP^A$

P = N P

$P = NP$

A

$A$

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

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