Consenso sobre P = NP em um mundo onde RP = NP

12

é amplamente conjecturado ser falsa.RP=NP

Mas imagine por um momento que seja verdade. Nesse caso, qual a probabilidade de ?P=NP

Em outras palavras: em um mundo onde , o que ainda pode ser visto como um obstáculo para acreditarmos em P = N P ?RP=NPP=NP

cc.complexity-theory complexity-classes conditional-results Giorgio Camerani
fonte
3
Em outras palavras, você está pedindo um oráculo em relação ao qual RP = NP, mas P NP. ≠
Yuval Filmus
Sim. Gostaria de saber se, em um mundo onde , as condições adicionais que precisam ser verdade para P ≠ N P são mais rigorosas e pouco provável que as condições adicionais que precisam ser verdade para P = N P . RP=NPP≠NPP=NP
Giorgio camerani
7
@ Yuval Filmus: Eu não sei se a questão é sobre barreira à relativização, mas se for, então existe um oráculo em relação ao qual RP = EXP (o que implica P ≠ RP = NP). Não consigo encontrar a referência para esse fato agora, mas é afirmado na observação após o Teorema 6, em Heller 1986, com referências a dois artigos de Kurtz e Heller, ambos nos trabalhos da "Conference on Computational Complexity Theory", em março de 1983.
Tsuyoshi Ito

Respostas:

14

Sinceramente, não acho que o Stack Exchange seja um local adequado para solicitar uma previsão futura. Apesar disso, vou postar uma resposta, porque é divertido brincar com a idéia de adivinhação.

Até onde eu sei, a possibilidade de P ≠ RP = NP não foi descartada. Além disso, existe uma língua Um tal que RP Um = EXP Um [Hel83, Kur83], o que implica imediatamente que P Um ≠ RP Um = NP Uma . (Eu não marquei [Hel83] ou [Kur83] e peguei o resultado e as referências da observação após o Teorema 6 em [Hel86].) Em outras palavras, até mesmo provar a implicação RP = NP ⇒ P = NP requer uma técnica não relativizante e, portanto, é compreensível que essa implicação não tenha sido comprovada.

(Lance Fortnow discutiu um resultado semelhante no blog da Computational Complexity: Resultados da Oracle são bons para você .)

Agora vamos passar para a parte de adivinhação.

Quanto esse resultado do oráculo diz sobre a probabilidade de P = NP no mundo em que RP = NP já foi provado? Não muito. No mínimo, não deve ser tomado como evidência de que no mundo onde RP = NP foi provado, ainda é provável que seja difícil provar P = NP. Nesse mundo, algumas técnicas novas e poderosas de não relativização são conhecidas pelo ser humano e, portanto, não seria razoável interpretar “requer uma técnica não relativizante” como evidência de dificuldade.

Falando de maneira mais ampla, se RP = NP tiver sido provado, apesar de todas as crenças (e também barreiras da técnica de prova) contra ele, é provável que nosso entendimento intuitivo atual sobre computação eficiente esteja muito errado. Obviamente, não podemos aplicar nossa intuição atual à razão do mundo em que nossa intuição atual falha espetacularmente. Não creio que possamos adivinhar um mundo assim, exceto pelo que foi rigorosamente provado.

Referências

[Hel83] Hans Heller. Em hierarquias polinomiais relativizadas que se estendem a dois níveis. Em Proceedings of Conference on Computational Complexity Theory , pp. 109-114, UC Santa Barbara, março de 1983.

[Hel86] Hans Heller. Em classes de complexidade exponencial e probabilística relativizadas. Information and Control , 71 (3): 231–243, dezembro de 1986. DOI: 10.1016 / S0019-9958 (86) 80012-2 .

[Kur83] S. Kurtz (Stuart A. Kurtz?). A estrutura fina de NP: Relativizações. Em Proceedings of Conference on Computational Complexity Theory , pp. 42–50, UC Santa Barbara, março de 1983.

Tsuyoshi Ito
fonte
"Obviamente, não podemos aplicar nossa intuição atual à razão sobre o mundo em que nossa intuição atual falha espetacularmente" ... essa é uma grande afirmação.
T ....