P / poly NP / poly tem implicações interessantes?

$P/poly = NP/poly$ implica , que por sua vez tem conseqüências interessantes como o colapso da hierarquia polinomial.$NP \subseteq P/poly$

Existem implicações interessantes para ?$P/poly \neq NP/poly$

O comentário de Emil Jeřábek responde à pergunta:

P / poli NP / poli é equivalente a NP P / poli$=$$\subseteq$

Observe o corolário

P / poli NP / poli implica P NP.$\neq$$\neq$

Prova de corolário:

1. P / poli NP / poli é equivalente a NP P / poli (comentário de Emil)$=$$\subseteq$$\ $
2. NP P / poli implica P / poli NP / poli (implícito em 1.)$\subseteq$$=$$\ $
3. P / poli NP / poli implica NP P / poli (equivalente a 2.)$\neq$$\not\subseteq$$\ $
4. NP P / poli implica P NP (P P / poli)$\not\subseteq$$\neq$$\ $$\subseteq$
5. P / poli NP / poli implica P NP (implicado em 3. e 4.)$\neq$$\neq$$\ $

Prova do comentário de Emil: É suficiente mostrar que NP P / poli implica P / poli NP / poli.$\subseteq$$=$

1. Então, vamos assumir NP P / poly.$\subseteq$
2. Como SAT NP existe e uma sequência de strings de aconselhamento com , um algoritmo determinístico que pode decida instâncias SAT de tamanho in time , se tiver acesso a . WLOG, esse algoritmo também pode decidir instâncias SAT de tamanho , porque podemos definir uma sequência modificada com , onde todas as strings de conselhos anteriores estão incluídas em .$\in$$p_{SAT}\geq k_{SAT}>0$$s_n$$\left|s_n\right|\leq n^{k_{SAT}}$$n$$\leq n^{p_{SAT}}$$s_n$$\leq n$$s'_n=s'_{n-1}s_n$$\left|s'_n\right|\leq n^{k_{SAT}+1}$$s'_n$
3. Agora vamos NP / poly ser uma linguagem arbitrária, para a qual precisamos mostrar P / poly. Existe e uma sequência de conselhos com e um algoritmo não determinístico que pode decidir instâncias de tamanho em tempo , se tiver acesso a .$L\in$$L\in$$p_L\geq k_L>0$$l_n$$\left|l_n\right|\leq n^{k_L}$$L$$n$$\leq n^{p_L}$$l_n$
4. Para cada com , uma instância de SAT de tamanho pode ser computada (em tempo ) que pode ser satisfeita exatamente se .$w$$|w|=n$$\leq c\cdot n^{p_L}$$O(n^{p_L})$$w\in L$
5. Portanto, para a sequência de strings de aconselhamento com , a combinação dos algoritmos determinísticos de 2. e 4. fornece um algoritmo determinístico que pode decidir instâncias de tamanho no tempo , se tiver acesso a .$t_n=l_ns_{c\cdot n^{p_L}}$$|t_n|\leq n^{k_L}+(c\cdot n^{p_L})^{k_{SAT}}$$L$$n$$O((c\cdot n^{p_L})^{p_{SAT}})$$t_n$
6. Como NP / poly era uma linguagem arbitrária, isso mostra NP / poly P / poly, sob a suposição de que NP P / poly.$L\in$$\subseteq$$\subseteq$

Todas as provas acima são relativizadas, porque a existência de problemas completos de NP também é verdadeira em mundos relativizados. Isso sugere que é inútil procurar uma prova de que P / poly NP / poly. No entanto, vamos resumir a seção de motivação removida$\neq$da pergunta como "A sequência de conselhos poderia ser um sistema axiomático formal (garantido automaticamente para ser consistente, sorriso maligno) cuja força está aumentando rapidamente com o comprimento da entrada, e NP é extremamente bom em explorar esse conselho". Se não se tomar muito cuidado com o fato de que "a existência de uma sequência de conselhos" apenas tenha significado "formal" em relação a um sistema formal fixo, é provável que essa configuração permita a construção de aparentes paradoxos. Mas a construção de tais paradoxos pode ser divertida, no entanto, e talvez eles até sugiram maneiras de construir provas de independência (para sistemas formais suficientemente fracos).