Czy P / poly

oznacza N P ⊆ P / P O l y , który z kolei ma wpływ interesujące jak załamania wielomianu hierarchii.$P/poly = NP/poly$$NP \subseteq P/poly$

Czy są interesujące implikacje dla ?$P/poly \neq NP/poly$

Komentarz Emila Jeřábka „odpowiada na pytanie:

P / poly NP / poly jest równoważne NP P / poly$=$$\subseteq$

Zwróć uwagę na następstwo

P / poly NP / poly implikuje P NP.$\neq$$\neq$

Dowód następstwa:

1. P / poly NP / poly jest równoważne NP P / poly (komentarz Emila)$=$$\subseteq$$\ $
2. NP P / poly implikuje P / poly NP / poli (implikowany przez 1.)$\subseteq$$=$$\ $
3. P / poly NP / poly implikuje NP P / poly (odpowiednik 2.)$\neq$$\not\subseteq$$\ $
4. NP P / poly implikuje P NP (P P / poly)$\not\subseteq$$\neq$$\ $$\subseteq$
5. P / poly NP / poly implikuje P NP (implikowane przez 3. i 4.)$\neq$$\neq$$\ $

Dowód komentarza Emila: Wystarczy wykazać, że NP P / poly implikuje P / poly NP / poly.$\subseteq$$=$

1. Załóżmy więc, że NP P / poly.$\subseteq$
2. Ponieważ SAT NP istnieje i sekwencja ciągów porad z , algorytm deterministyczny, który może decyduj o instancjach SAT o rozmiarze w czasie , jeśli ma on dostęp do . WLOG, ten algorytm może również decydować o instancjach SAT o rozmiarze , ponieważ możemy zdefiniować zmodyfikowaną sekwencję pomocą , gdzie wszystkie poprzednie ciągi porad zawarte są w .$\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. Teraz niech NP / poly będzie dowolnym językiem, dla którego musimy pokazać P / poly. Istnieje i sekwencja ciągów porad z i niedeterministyczny algorytm, który może decydować o wystąpieniach o rozmiarze w czasie , jeśli ma dostęp do .$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. Dla każdego w instancja SAT wielkości może być obliczona (w czasie ), który jest spe dokładnie, jeśli .$w$$|w|=n$$\leq c\cdot n^{p_L}$$O(n^{p_L})$$w\in L$
5. Tak więc dla sekwencji ciągów porad z , kombinacja algorytmów deterministycznych z 2. i 4. daje algorytm deterministyczny, który może decydować o wystąpieniach o rozmiarze w czasie , jeśli ma dostęp do .$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. Ponieważ NP / poly był dowolnym językiem, pokazuje to NP / poly P / poly, przy założeniu, że NP P / poly.$L\in$$\subseteq$$\subseteq$

Wszystkie powyższe dowody relatywizują się, ponieważ istnienie problemów z NP-zupełnością jest również prawdziwe w relatywizowanych światach. Sugeruje to, że bezowocne jest poszukiwanie dowodu, że P / poly NP / poly. Podsumujmy jednak usuniętą sekcję motywacji$\neq$od pytania jako „Ciąg porad może być formalnym systemem aksjomatycznym (automatycznie gwarantowanym, że jest spójny, zły uśmiech), którego siła szybko rośnie wraz z długością wejściową, a NP jest wyjątkowo dobry w wykorzystywaniu tej porady”. Jeśli ktoś nie jest bardzo ostrożny, że „istnienie sekwencji żądań porady” ma jedynie „formalne” znaczenie w stosunku do ustalonego systemu formalnego, taka konfiguracja prawdopodobnie pozwoli na zbudowanie pozornych paradoksów. Ale konstruowanie takich paradoksów może być jednak zabawne, a może nawet sugerują sposoby konstruowania dowodów niezależności (dla wystarczająco słabych systemów formalnych).