Czy P / poly

oznacza , 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$

cc.complexity-theory conditional-results advice-and-nonuniformity

— Thomas Klimpel
źródło

jestrównoważnydo

P / p o l y = N P / p o l y

$\mathrm{P}/\mathrm{poly}=\mathrm{NP}/\mathrm{poly}$

N P \subseteq P / p o l y

$\mathrm{NP}\subseteq\mathrm{P}/\mathrm{poly}$

— Emil Jeřábek

\neq

$\neq$

⊈

$\not\subseteq$

@Kaveh: czy usunięcie motywacji jest naprawdę tym, co powinniśmy robić? Wprowadził mnie w rzeczy, których wcześniej nie spotkałem, i nie jest tak, że nie został podzielony. To nie jest Twitter.

— András Salamon,

@ EmilJeřábek Chyba już to mam. NP P / poly implikuje P / poly = NP / poly, ponieważ algorytm deterministyczny może uzyskać zarówno własny ciąg porad, aby stać się tak potężny jak NP, wraz z ciągiem porad dla języka z NP / poly, a to jest wystarczy do podjęcia decyzji w tym języku.

\subseteq

$\subseteq$

— Thomas Klimpel

@ThomasKlimpel: Tak, dokładnie.

— Emil Jeřábek

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:

P / poly NP / poly jest równoważne NP P / poly (komentarz Emila) $=$ $\subseteq$ $\$
NP P / poly implikuje P / poly NP / poli (implikowany przez 1.) $\subseteq$ $=$ $\$
P / poly NP / poly implikuje NP P / poly (odpowiednik 2.) $\neq$ $\not\subseteq$ $\$
NP P / poly implikuje P NP (P P / poly) $\not\subseteq$ $\neq$ $\$ $\subseteq$
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$ $=$

Załóżmy więc, że NP P / poly. $\subseteq$
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$
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$
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$
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$
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).

— Thomas Klimpel
źródło