Um oráculo é útil se você não pode controlar as instâncias de entrada?

Digamos que seja um oráculo para um problema no , mas não posso chamar esse oráculo com nenhuma instância de entrada. Em vez disso, sempre que chamo , recebo uma instância e solução aleatórias. Portanto, eu sei que é realmente capaz de resolver problemas difíceis arbitrários , apenas não consigo especificar qual deles eu quero resolver.$F$$\mathbb{NP}$$F$$F$$\mathbb{NP}$

É possível usar esse oráculo para resolver um problema completo em mais rapidamente? Meu intestino diz que não, porque o uso ingênuo do oráculo ainda requer tempo chamando o oráculo o suficiente para verificar todas as soluções. Eu simplesmente não consigo pensar em uma maneira de provar isso.$\mathbb{NP}$$O(2^n)$

Como o Xodarap apontou, se você precisar que seu algoritmo com o “oráculo aleatório” sempre produza a resposta correta, o oráculo aleatório será inútil. O problema se torna mais interessante se permitirmos uma pequena probabilidade de erro (onde a probabilidade é com relação à instância aleatória escolhida pelo oráculo).

Além disso, como Vor apontou nos comentários sobre a questão, não faz sentido dizer "instância aleatória" sem especificar uma distribuição de probabilidade. Uma das suposições razoáveis ​​a serem feitas aqui é que essa instância aleatória é escolhida uniformemente aleatoriamente no conjunto de todas as cadeias de comprimento p ( n ), em que n é o comprimento de entrada ep é um polinômio fixo. Poderíamos fazer outras suposições mais fracas sobre a distribuição de probabilidade.

Aqui, tornaremos a suposição bastante geral e mostraremos que a existência de um algoritmo de tempo polinomial aleatório com um "oráculo aleatório" para problemas completos de NP tem uma conseqüência surpreendente, mesmo sob essa suposição fraca.

Vamos abandonar o requisito de que o “oráculo aleatório” resolva um problema no NP (em uma instância escolhida aleatoriamente). Agora, o "oráculo aleatório" pode ser qualquer distribuição de probabilidade predeterminada sobre cadeias de comprimento polinomial e, toda vez que é solicitado, emite uma cadeia de acordo com essa distribuição de probabilidade. O único requisito é que essa distribuição de probabilidade dependa apenas do comprimento da entrada. Observe que seu modelo é realmente um caso especial desse modelo. No seu modelo, a distribuição de probabilidade é requerida para ter a seguinte forma: ela primeiro escolhe uma instância uniformemente aleatória y de um conjunto, dependendo do comprimento da entrada e, em seguida, retorna um par ( y , g ( y )), onde g: {0, 1} * → {0, 1} é a função característica de algum problema de decisão no NP. Agora permitimos qualquer distribuição de probabilidade, desde que a distribuição seja determinada apenas pelo comprimento da entrada.

Um "oráculo" desta forma geral é chamado de conselho aleatório . A classe de problemas de decisão que pode ser decidida por um algoritmo de tempo polinomial aleatório com um conselho aleatório (com erro bilateral de dois lados) é chamada BPP / rpoly, e sabe-se que essa classe é igual a P / poli . (A inclusão BPP / rpoly⊆P / poly pode ser comprovada da mesma maneira que uma inclusão conhecida BPP⊆P / poly. Para uma prova disso, consulte, por exemplo, o Teorema 6.3 de Goldreich [Gol08].)

Isso significa que, se um problema completo de NP puder ser resolvido no seu modelo, então NP⊆P / poli. No entanto, sabe-se que NP⊆P / poly implica que a hierarquia polinomial cai para o segundo nível [KW98, Cai07]. A maioria dos teóricos da complexidade considera uma grande surpresa o colapso da hierarquia polinomial. Se acreditarmos que a hierarquia polinomial não entra em colapso, os problemas completos de NP não podem ser resolvidos eficientemente com o "oráculo aleatório" em seu sentido.

Referências

[Cai07] Jin-Yi Cai. S ₂ ^p ⊆ ZPP ^NP . Journal of Computer and System Sciences , 73 (1): 25–35, fevereiro de 2007. DOI: 10.1016 / j.jcss.2003.07.015 .

[Gol08] Oded Goldreich. Complexidade Computacional: Uma Perspectiva Conceitual . Cambridge University Press, 2008.

[KW98] Johannes Köbler e Osamu Watanabe. Novas conseqüências de colapso de NP com pequenos circuitos. SIAM Journal on Computing , 28 (1): 311–324, 1998. DOI: 10.1137 / S0097539795296206 .

Vamos pensar especificamente no problema NP-completo favorito de todos: 3SAT.

É possível (embora improvável) que cada vez que você chame seu oráculo, ele lhe dê uma tarefa para a mesma instância. Especificamente, cada vez que você pode atribuir uma atribuição para a frase trivial:

Mas você já sabe a tarefa para isso. Portanto, seu Oracle não pode ser útil.

Mais formalmente, se chamarmos seu oráculo de , então (assumindo ...)$A$$P^A\not=NP$$P\not=NP$