Czy twierdzenie Kannana implikuje, że NEXPTIME ^ NP ⊄ P / poly?

Czytałem artykuł Buhrmana i Homera „Obwody wielobiegunowe, Prawie rzadkie wyrocznie i hierarchia wykładnicza” .

Na dole strony 2 zauważają, że wyniki sugerują, że nie ma obwodów wielomianowych. Wiem, że w wykładniczej hierarchii czasu to po prostu , a także wiem, że wynikiem jest to, że tak, że . Oczywiście twierdzenie NIE mówi (aby tak było, musielibyśmy wykazać, że tak, że , Nie rozumiem jednak, jak sugeruje to wynik Kannana $NEXPTIME^{NP}$ $NEXPTIME^{NP}$ $\Sigma_2EXP$ $\forall c\mbox{ }\exists L\in\Sigma_2P$ $L \not\in Size(n^c)$ $\Sigma_2P \not\subset P/poly$ $\exists L\in\Sigma_2P$ $\forall c$ $L \not\in Size(n^c)$ $NEXPTIME^{NP} \not\subset P/poly$ ?

— Gilles „SO- przestań być zły”
źródło

Być może jest to bardziej odpowiednie dla cstheory.se.

— Yuval Filmus

@YuvalFilmus Ok, dzięki. Jeśli moderator uważa, że jest to bardziej odpowiednie dla cstheory.se, możesz go przenieść.

Jest to obecnie również zestaw problemów z cs354 ...: - / ... wyraźnie poinstruowałem uczniów, żeby nie pytali o Internet, więc „Lorraine” lepiej mieć nadzieję, że nie wezmą mojej klasy.

— Ryan Williams

@Sasho, myślę, że dobrze byłoby to zrobić, przynajmniej do upływu terminu zlecenia.

— Kaveh

@Turbo Chyba równie dobrze mogę, mam nadzieję, że nie dotyczy to obecnie problemu innej osoby.

— Sasho Nikolov,

Ta wersja odpowiedzi zawiera informacje zwrotne od Emila Jeřábka.

O ile widzę, głównym zwrotem jest to, że w złożoność obwodu wykładniczego. W szczególności napraw kodowanie binarne obwodów boolowskich i zdefiniuj jako język zdefiniowany przez $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ $L$

$L_n$ nie decyduje żaden obwód o rozmiarze , i $2^{n/2}$

każdy język który poprzedza leksykograficznie jest określony przez jakiś obwód o wielkości co najwyżej , $L'_n \subseteq \{0,1\}^n$ $L_n$ $C$ $2^{n/2}$

gdzie notacja oznacza wycinek . $L_n$ $L_n = L \cap \{0,1\}^n$

Aby to zrobić w czasie wykładniczym za pomocą , możesz użyć wyszukiwania binarnego dla podzbiorów (pomyśl o nich jako o liczbach całkowitych ), aby znaleźć pierwszą taki zestaw, który ma złożoność obwodu . Po prostu zachowujesz bieżące przypuszczenie i używasz wyroczni, aby sprawdzić, czy istnieje o złożoności obwodu co najmniej . Ponieważ daje to urządzenie w który spisuje całego wycinka wyraźnie możemy również zdecydować członkostwa w , a zatem w . $\Sigma_2^\mathsf{P}$ $\{0,1\}^n$ $2^n$ $> 2^{n/2}$ $L_n$ $L'_n \prec_{\text{lex}} L_n$ $2^{n/2}$ $\mathsf{EXP}^{\Sigma^\mathsf{P}_2}$ $L_n$ $L_n$ $L$

Jest to bardzo podobne do argumentu Kannana, ale zostało powiększone i usprawnione, aby wykorzystać czas wykładniczy. W takim razie powinieneś być w stanie użyć skalowanej wersji twierdzenia Karp-Lipton, aby pokazać, że jeśli , to , a analizę przypadku możesz przeprowadzić na dowód Kannana. $\mathsf{NEXP} \subseteq \mathsf{P/poly}$ $\mathsf{EXP}^{\Sigma^\mathsf{P}_2} \subseteq \mathsf{NEXP}^{\mathsf{NP}}$

— Sasho Nikolov
źródło

AFAICS twój opis podaje bezpośrednio język , a nie .

{E X P}^{Σ_{2}^{P}}

$\mathrm{EXP}^{\Sigma^P_2}$

{N E X P}^{Σ_{3}^{P}}

$\mathrm{NEXP}^{\Sigma^P_3}$

— Emil Jeřábek,

@ EmilJeřábek Mój mózg nigdy nie był w stanie przetwarzać maszyn wyroczni. I głębokość kwantyfikatora cztery: jest w jeśli istnieje obwód o rozmiarze taki, że i [dla wszystkich obwodów o rozmiarze istnieje słowo dla którego ] i [dla wszystkich poprzedzających w porządku leksykalnym istnieje obwód o rozmiarze najwyżej st dla wszystkich

w \in {0, 1}^{n}

$w \in \{0,1\}^n$

L

$L$

C^{*}

$C^*$

\leq 2^{n}

$\le 2^n$

C^{*} (w) = 1

$C^*(w) = 1$

C

$C$

2^{n / 2}

$2^{n/2}$

w^{'} \in {0, 1}^{n}

$w' \in \{0,1\}^n$

C (w^{'}) \neq C (w)

$C(w') \neq C(w)$

C^{'}

$C'$

C^{*}

$C^*$

C^{″}

$C''$

2^{n / 2}

$2^{n/2}$

w^{'} \in {0, 1}^{n}

$w' \in \{0,1\}^n$

C^{'} (w^{'}) = C^{″} (w^{'})

$C'(w') = C''(w')$ ]. To wydaje się być czwartym poziomem hierarchii wykładniczej. Co to jest w zapisie wyroczni?

— Sasho Nikolov,

Po pierwsze: „istnieje słowo ...” i podobny uniwersalny kwantyfikator pod koniec nie liczą się, ponieważ mają rozmiar liniowy, a zatem można je obliczyć deterministycznie w czasie wykładniczym. Po drugie, najbardziej zewnętrzny kwantyfikator można symulować deterministycznie w czasie wykładniczym za pomocą wyszukiwania binarnego.

— Emil Jeřábek,

Oznacza to, że leksykograficznie pierwszą funkcję boolowską na danych wejściowych, która nie ma obwodów o rozmiarze można znaleźć przez wyszukiwanie binarne w czasie wykładniczym z wyrocznią dla predykatu „istnieje funkcja leksykograficznie poprzedzająca który nie jest obliczalny dla obwodu o wielkości ".

f

$f$

n

$n$

2^{n / 2}

$2^{n/2}$

f^{'}

$f'$

f

$f$

2^{n / 2}

$2^{n/2}$

— Emil Jeřábek,

@SashoNikolov Więc nadal działa od . Jednak nie możemy używać, jeśli następnie zastosować Karpa-Lipton w cstheory.stackexchange.com/questions/39837/... . Mamy więc i . To nie działa dla .

E X P^{Σ_{2}^{P}} \subseteq N E X P^{Σ_{3}^{P}}

$EXP^{\Sigma_2^P}\subseteq NEXP^{\Sigma_3^P}$

N E X P \subseteq i . o . P / p o l y

$NEXP\subseteq i.o.P/poly$

E X P^{P P} ⊈ i . o . P / p o l y

$EXP^{PP}\not\subseteq i.o.P/poly$

N E X P^{Σ_{3}^{P}} ⊈ i . o . P / p o l y

$NEXP^{\Sigma_3^P}\not\subseteq i.o.P/poly$

N E X P^{N P}

$NEXP^{NP}$

— T ....