Załamuje się przy założeniu, że

Wiadomo, że w przypadku następnie wielomian hierarchia zapada się Ď P 2 i M A = A M .$NP\subseteq P/Poly$$\Sigma_2^{P}$$MA = AM$

Jakie są najsilniejsze znane upadki, jeśli ?$NEXP\subseteq P/Poly$

Wierzę najsilniejszy jest . Zostało to udowodnione przez Impagliazzo Kabanets i Wigderson.$NEXP = MA$

Zobacz https://scholar.google.com/scholar?cluster=17275091615053693892&hl=pl&as_sdt=0,5&sciodt=0,5

Byłbym również zainteresowany, aby wiedzieć o silniejszych załamaniach niż to.

Edycja (8/24): OK, myślałem o potencjalnie silniejszym załamaniu, które zasadniczo wynika z dowodów powyższego powiązanego papieru. Ze względu oznacza N E X P = E X P (patrz powyższy odnośnik), oraz e X P jest zamknięty pod dopełniacza także mieć N E X P zamyka się pod dopełniacza, a więc N E X P = M A ∩ c o M $NEXP \subset P/poly$$NEXP = EXP$$EXP$$NEXP$$NEXP = MA \cap coMA$, który jest trochę silniejszy. Rzeczywiście, hipoteza oznacza, że dla każdego i języku, pojedynczy łańcuch świadka w n mogą być stosowane w odpowiednim protokole MA wszystkich tak- przypadków danej długości n , to również N E X P = O M A ∩ c o O M A (gdzie O M A = „Oblivious MA”, patrz Fortnow-Santhanam-me http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&rep=rep1&type=pdf$NEXP$$w_n$$n$$NEXP = OMA \cap coOMA$$OMA$). Te dodatkowe właściwości, chociaż techniczne, mogą okazać się przydatne w niektórych argumentach w dolnych granicach obwodu.

Edycja 2: Wygląda na to, że Andrew Morgan już to podkreślił. Ups :)

Dzieje się mnóstwo fajnych rzeczy. Większość tych, które znam, zaczyna się od papieru IKW . Tam $\textrm{NEXP} = \textrm{MA}$ zwinięcie NEXP = MA i (myślę) jest najsilniejszym dosłownym załamaniem klas złożoności, jakie znamy. Istnieją jednak inne rodzaje „załamań”, które moim zdaniem należy podkreślić.

Najważniejsze, jak sądzę, jest właściwość „uniwersalnego zwięzłego świadka” (również z pracy IKW). Po pierwsze, daje narzędzie, z którego wiele innych zawaleń ma bezpośrednie konsekwencje; po drugie, ostatnie dolne granice obwodu (np. tu i tutaj ) dla $\textsf{NEXP}$ wykorzystują to połączenie. W skrócie, nieruchomość mówi, że dla każdego $\textsf{NEXP}$ języka $L$ , a każdy $\textsf{NEXP}$ -machine $M$ decydując $L$ , każdy $x \in L$ ma zwięźle opisania świadectwo według $M$ . Formalnie istnieje wielomian $p$ zależny od$M$ tak, że dla każdego$x \in L$ istnieje obwód$C_x$ o wielkości$p(|x|)$ tak że tabela prawdy$C_x$ jest sekwencją niedeterministycznych wyborów dla$M$ które prowadzą do akceptacji na wejściu$x$ .

Przydaje się zwięzłość świadków, ponieważ można od razu przerobić wiele innych upadków. Na przykład trywialnie wynika, że $\textsf{NEXP} = \textsf{coNEXP} = \textsf{EXP}$ . Na przykład załóżmy, że $L$ jest $\textsf{NEXP}$ poprzez $\textsf{NEXP}$ -machine $M$ . Właściwość zwięzłego świadka mówi, że istnieje wielomian $p$ więc $M$ ma zwięzłych świadków wielkości $p$ . Możemy wtedy zdecydować $L$ w $\textsf{EXP}$ , na wejściu $x$ , brutalnie wymuszając wszystkie obwody wielkości co najwyżej $p(|x|)$ i sprawdzenie, czy kodują sekwencję wyborów, które prowadzą doakceptacji$M$ na wejściu$x$ . Możesz to połączyć z (wcześniej znanym z interaktywnych dowodów) wynikiem$\textsf{EXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{EXP} = \textsf{MA}$ do zawarcia$\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly} \implies \textsf{NEXP} = \textsf{MA}$ .

Warto podkreślić, że możemy wybrać $M$ a tym samym formę świadków. Na przykład można faktycznie wywnioskować z „ $\textsf{NEXP}$ ma uniwersalnych zwięzłych świadków”, że $\textsf{NEXP} = \textsf{OMA} = \textsf{co-OMA}$ . Tutaj $\textsf{OMA}$ jest „oblivious-MA”, co oznacza, że ​​istnieje uczciwy Merlin, który zależy tylko od długości wejściowej. Łatwo zauważyć, że $\textsf{OMA} \subseteq \textsf{P}/\textrm{poly}$ , więc w zasadzie daje to normalną formę $\textsf{NEXP}$ języków NEXP w $\textsf{P}/\textrm{poly}$ przy założeniu, że $\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$na pierwszym miejscu. Oto jeden ze sposobów, aby zobaczyć upadek do $\textsf{OMA}$ :

$L \in \mathsf{NEXP}$$M$$\mathsf{NEXP}$$M'$$n$$N$$1$$2^n$$x$$n$$w_x$$M(x,w_x)$$M'(N)$$M$$N$$x$$M'$$C$$(x,i) \mapsto$$i$$w_x$$N$$L$$n$$M'$$N$$M$$n$$M'$$M$

$\textsf{NEXP} = \textsf{PCP}[\textrm{poly}, \textrm{poly}]$$M$$\textsf{NEXP}$$\textsf{NEXP} = \textsf{OMA}$

$L$$M'$$\mathsf{NEXP}\subseteq\mathsf{P/poly}$$\mathsf{NEXP}=\mathsf{EXP}$$L$

$\textsf{NEXP}=\textsf{MA}$$\textsf{NEXP}=\textsf{PSPACE}$$\textsf{PSPACE}$$\textsf{PSPACE}$$\textsf{NEXP}$$\textsf{NEXP} \ne \textsf{PSPACE}$$\textsf{NEXP} = \textsf{PSPACE}$$\textsf{NEXP}$ $\textsf{NEXP}$$\textsf{EXP}$$\textsf{BPP}$$\textsf{EXP}$$\textsf{NEXP} \subseteq \textsf{P}/\textrm{poly}$