Czy NPI jest zawarty w P / poly?

Przypuszcza się, że ponieważ odwrotność oznaczałaby . Twierdzenie Ladnera stwierdza, że ​​jeśli a następnie . Wydaje się jednak, że dowód nie uogólnia na więc możliwość ie wydaje się otwarty.$\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$$\mathsf{PH} = \Sigma_2$$\mathsf{P} \ne \mathsf{NP}$$\mathsf{NPI} := \mathsf{NP} \setminus(\mathsf{NPC} \cup \mathsf{P}) \ne \emptyset$$\mathsf{P}/\text{poly}$$\mathsf{NPI} \subset \mathsf{P}/\text{poly}$$\mathsf{NP} \subset \mathsf{NPC} \cup \mathsf{P}/\text{poly}$

Zakładając, że (a nawet, że hierarchia wielomianowa nie zawala się na żadnym poziomie), jest znany jako prawda czy fałsz? Jakie dowody można przedstawić za i przeciw?$\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$$\mathsf{NPI} \subset \mathsf{P}/\text{poly}$

Oto możliwa alternatywa dla argumentu wypełniającego, oparta na uogólnieniu twierdzenia Ladnera przez Schöninga. Aby zrozumieć argument, musisz mieć dostęp do tego dokumentu (który niestety będzie dla wielu za ścianą płatną):

Uwe Schöning. Jednolite podejście do uzyskiwania zestawów diagonalnych w klasach złożoności. Theoretical Computer Science 18 (1): 95-103, 1982.

Zastosujemy główne twierdzenie z tego artykułu dla i będących językami, a i będącymi klasami złożoności w następujący sposób:A 2 C 1 C$A_1$$A_2$$\mathsf{C}_1$$\mathsf{C}_2$

• $A_1 = \varnothing$ (lub dowolny język w )$\mathsf{P}$
• $A_2 = \text{SAT}$
• $\mathsf{C}_1 = \mathsf{NPC}$
• $\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$

Dla jasności udowodnimy, że implikuje .N P I ⊈ P / p o l $\mathsf{NP} \not\subseteq \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

Zakładając, że mamy i . Oczywiste jest, że i są zamknięte w skończonych odmianach. Artykuł Schöninga zawiera dowód, że jest rekurencyjnie prezentowalny (dokładną definicję można znaleźć w artykule), a najtrudniejszą częścią argumentu jest udowodnienie, że jest rekurencyjnie prezentowalny.A 1 ∉ C 1 A 2 ∉ C 2 C 1 C 2 C 1 C$\mathsf{NP} \not\subseteq \mathsf{P/poly}$$A_1\not\in\mathsf{C}_1$$A_2\not\in\mathsf{C}_2$$\mathsf{C}_1$$\mathsf{C}_2$$\mathsf{C}_1$$\mathsf{C}_2$

Zgodnie z tymi założeniami twierdzenie implikuje, że istnieje język który nie jest ani w ani w ; i biorąc pod uwagę, że , utrzymuje, że jest do redukcji Karpa do , a zatem . Ponieważ znajduje się w ale nie jest -kompletny, ani w , wynika z tego, że .C 1 C 2 A 1 ∈ P A A 2 A ∈ N P A N P N P N P ∩ P / p o l y N P I ⊈ P / p o l $A$$\mathsf{C}_1$$\mathsf{C}_2$$A_1\in\mathsf{P}$$A$$A_2$$A\in\mathsf{NP}$$A$$\mathsf{NP}$$\mathsf{NP}$$\mathsf{NP} \cap \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

Pozostaje udowodnić, że można rekurencyjnie prezentować. Zasadniczo oznacza to, że istnieje wyraźny opis sekwencji deterministycznych maszyn Turinga które zatrzymują się na wszystkich wejściach i są takie, że . Jeśli w moim argumencie występuje błąd, prawdopodobnie jest on tutaj, a jeśli naprawdę chcesz użyć tego wyniku, zrób to ostrożnie. W każdym razie, poprzez dopasowywanie do wszystkich niedeterministycznych maszyn Turinga w czasie wielomianowym (które można symulować deterministycznie, ponieważ nie dbamy o czas działania każdegoM 1 , M 2 , … N P ∩ P / p o l y = { L ( M k ) : k = 1 , 2 , … } M k M k M $\mathsf{NP} \cap \mathsf{P/poly}$$M_1, M_2, \ldots$$\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$$M_k$) i wszystkie wielomiany reprezentujące górne granice wielkości rodziny obwodów boolowskich dla danego języka, uważam, że nie jest trudno uzyskać wyliczenie, które działa. Zasadniczo, każdy może przetestować, czy odpowiadający mu NTM czasu wielomianowego zgadza się z pewną rodziną obwodów wielomianowych aż do długości ciągu wejściowego, który jest podany, przeszukując wszystkie możliwe obwody boolowskie. Jeśli istnieje zgoda, wyprowadza tak jak NTM, w przeciwnym razie odrzuca (iw rezultacie reprezentuje skończony język).$M_k$$M_k$

Podstawowa intuicja stojąca za argumentem (ukrytym w wyniku Schöninga) jest taka, że ​​nigdy nie można mieć dwóch „ładnych” klas złożoności (tj. Tych z rekurencyjnymi prezentacjami), które są rozłączne i siedzą naprzeciwko siebie. „Topologia” złożonych klas nie pozwala na to: zawsze możesz poprawnie zbudować język między dwiema klasami, w jakiś sposób naprzemiennie między nimi dla bardzo długich odcinków długości wejściowych. Twierdzenie Ladnera pokazuje to dla i , a uogólnienie Schöninga pozwala zrobić to samo dla wielu innych klas.N P $\mathsf{P}$$\mathsf{NPC}$

Chciałbym tylko zapisać pewną wersję argumentu wypełniającego, jak opisano w komentarzach. Nie rozumiem, dlaczego potrzebna jest luka. Chcemy pokazać, że jeśli NP nie jest zawarty w P / poli, to istnieje problem pośredniego NP nie zawarty w P / poli.

Istnieje funkcja nieograniczona taka że SAT nie ma obwodów o rozmiarze mniejszym niż , a zatem istnieje funkcja która jest nieograniczona, rośnie, a . Niech SAT 'oznacza język uzyskany przez wypełnienie ciągów SAT o długości od do . Następnie:n f ( n ) g g ( n ) = o ( f ( n ) ) n n g ( n $f$$n^{f(n)}$$g$$g(n)=o(f(n))$$n$$n^{g(n)}$

• SAT 'jest w NP (patrz poniżej!)
• SAT 'nie jest w P / poly: biorąc pod uwagę obwody o rozmiarze dla SAT', otrzymujemy obwody o rozmiarze dla SAT, ale jest to mniej niż dla niektórych .n g ( n ) k n f ( n )$n^k$$n^{g(n)k}$$n^{f(n)}$$n$
• Nie ma redukcji P / poli z SAT do SAT ': załóżmy, że dla sprzeczności istnieją obwody o rozmiarze dla SAT, pozwalając na bramki SAT'. Odbiór na tyle duże, że i pozwolić . Każda bramka SAT 'w ma co najwyżej wejść. Usuwając wejścia dopełniania, możemy przyciąć bramki SAT 'w do bramki SAT z wejściami mniejszymi niż , które możemy symulować za pomocą - powstałe bramki SAT mają co najwyżej Wejścia . Powtarzając to i traktując , SAT miałby obwody mniej więcej wielkościn k N g ( $C_n$$n^k$$N$n>NCnnkCn$g(\sqrt{N}) > 2k$$n>N$$C_n$$n^k$$C_n$ C$\sqrt{n}$ nk/2CNO(nknk/2nk/4…)≈O(n2k)nf(n)$C_{\sqrt{n}}$$n^{k/2}$$C_N$$O(n^k n^{k/2} n^{k/4} \dots) \approx O(n^{2k})$ która jest mniejsza niż dla niektórych .$n^{f(n)}$$n$

Edytować:

Wybór jest nieco skomplikowany. Jeśli jesteś zadowolony z umieszczenia SAT w obiecującej wersji NP, ten bit jest niepotrzebny.$g$

Zdefiniuj jako maksymalną liczbę całkowitą, tak aby nie było obwodu o rozmiarze dla długości łańcuchów dla SAT. Zdefiniuj za pomocą algorytmu, który oblicza dla i zatrzymuje się po czasie lub gdy , i zwraca podłogę pierwiastka kwadratowego z najwyższej wartości znalezionej w tym czasie . Zatem jest nieograniczone, a i można obliczyć w czasie . Zauważ teraz, że powyższe argumenty polegają tylko na tym, że SAT nie ma obwodów o rozmiarze dla nieskończenie wielun f ( n )$f(n)$$n^{f(n)}$$n$f ( m ) m = 1 , 2 , … n m = n g ( n ) lim inf g ( n ) / f ( n ) = 0 g ( n ) n n f ( n )$g(n)$$f(m)$$m=1,2,\dots$$n$$m=n$$g(n)$$\liminf g(n)/f(n)=0$$g(n)$$n$$n^{f(n)}$$n$.

Interesujące byłoby również zobaczyć dowód, wydmuchując dziury w SAT, jak w http://blog.computationalcomplexity.org/media/ladner.pdf . Bez wymogu NP jest to dość łatwe: istnieje sekwencja taka, że ​​żaden rozmiar os obwodu wykrywa ciągów SAT o długości ; ogranicz SAT do ciągów o długości dla niektórych .( n k ) k n n 2 2 i$n_1<n_2<\dots$$(n_k)^k$$n$$n_{2^{2^i}}$$i$

(NPI P / poly) (P NP)$\nsubseteq$$\implies$$\neq$