Le NPI est-il contenu dans P / poly?

On que car l'inverse impliquerait . Le théorème de Ladner établit que si alors . Cependant, la preuve ne semble pas généraliser à donc la possibilité ie semble ouvert.$\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}$

En supposant que (ou même que la hiérarchie polynomiale ne s'effondre à aucun niveau), est connu pour être vrai ou faux? Quelles preuves peuvent être avancées pour ou contre?$\mathsf{NP} \nsubseteq \mathsf{P}/\text{poly}$$\mathsf{NPI} \subset \mathsf{P}/\text{poly}$

Voici une alternative possible à un argument de remplissage, basé sur la généralisation de Schöning du théorème de Ladner. Pour comprendre l'argument, vous devez avoir accès à ce document (qui sera malheureusement derrière un mur de rémunération pour beaucoup):

Uwe Schöning. Une approche uniforme pour obtenir des ensembles diagonaux dans les classes de complexité. Informatique théorique 18 (1): 95-103, 1982.

Nous appliquerons le théorème principal de cet article pour et A 2 étant des langues et C 1 et C 2 étant des classes de complexité comme suit:$A_1$$A_2$$\mathsf{C}_1$$\mathsf{C}_2$

• (ou n'importe quelle langue en P )$A_1 = \varnothing$$\mathsf{P}$
• $A_2 = \text{SAT}$
• $\mathsf{C}_1 = \mathsf{NPC}$
• $\mathsf{C}_2 = \mathsf{NP} \cap \mathsf{P/poly}$

Par souci de clarté, le fait que nous prouverons que implique N P I ⊈ P / p o l y .$\mathsf{NP} \not\subseteq \mathsf{P/poly}$$\mathsf{NPI} \not\subseteq \mathsf{P/poly}$

Dans l'hypothèse que nous avons A 1 ∉ C 1 et A 2 ∉ C 2 . Il est clair que C 1 et C 2 sont fermés sous des variations finies. L'article de Schöning comprend une preuve que C 1 est récursivement présentable (dont la définition précise peut être trouvée dans l'article), et la partie la plus difficile de l'argument est de prouver que C 2 est récursivement présentable.$\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$

Sous ces hypothèses, le théorème implique qu'il existe un langage qui n'est ni en C 1 ni en C 2 ; et étant donné que A 1 ∈ P , il estime que A est Karp réductible à A 2 , et donc A ∈ N P . Étant donné que A est dans N P mais n'est ni N P- complet ni dans N P ∩ P / p o l y , il s'ensuit que N $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}$

Il reste à prouver que est présentable récursivement. Fondamentalement, cela signifie qu'il existe une description explicite d'une séquence de machines de Turing déterministes M 1 , M 2 , … qui s'arrêtent toutes sur toutes les entrées et sont telles que N P ∩ P / p o l y = { L ( M k ) : k = 1 , 2 , … $\mathsf{NP} \cap \mathsf{P/poly}$$M_1, M_2, \ldots$$\mathsf{NP} \cap \mathsf{P/poly} = \{L(M_k):k=1,2,\ldots\}$. S'il y a une erreur dans mon argument, c'est probablement ici, et si vous avez vraiment besoin d'utiliser ce résultat, vous voudrez le faire avec soin. Quoi qu'il en soit, en alignant sur toutes les machines de Turing non déterministes à temps polynomial (qui peuvent être simulées de manière déterministe parce que nous ne nous soucions pas du temps de fonctionnement de chaque ) et tous les polynômes, représentant les limites supérieures de la taille d'une famille de circuits booléens pour un étant donné la langue, je pense qu'il n'est pas difficile d'obtenir un dénombrement qui fonctionne. En substance, chaque M k peut tester que son NTM à temps polynomial correspondant est en accord avec une famille de circuits de taille polynomiale jusqu'à la longueur de la chaîne d'entrée qui lui est donnée en recherchant sur tous les circuits booléens possibles. S'il y a accord, M $M_k$$M_k$$M_k$ sorties comme le ferait le NTM, sinon il rejette (et en conséquence représente un langage fini).

L'intuition de base derrière l'argument (qui est caché dans le résultat de Schöning) est que vous ne pouvez jamais avoir deux classes de complexité "agréables" (c'est-à-dire, celles avec des présentations récursives) étant disjointes et assises l'une contre l'autre. La "topologie" des classes complexes ne le permet pas: vous pouvez toujours construire correctement un langage entre les deux classes en alternant d'une manière ou d'une autre entre les deux pour des tronçons extrêmement longs de longueurs d'entrée. Le théorème de Ladner le montre pour et N P C , et la généralisation de Schöning vous permet de faire de même pour de nombreuses autres classes.$\mathsf{P}$$\mathsf{NPC}$

Je voudrais juste écrire une version d'un argument de remplissage comme décrit dans les commentaires. Je ne vois pas pourquoi un écart est nécessaire. Nous voulons montrer que si NP n'est pas contenu dans P / poly alors il y a un problème NP-intermédiaire non contenu dans P / poly.

Il existe une fonction illimitée telle que SAT n'a pas de circuits de taille inférieure à n f ( n ) , et il existe donc une fonction g illimitée, croissante et g ( n ) = o ( f ( n ) ) . Soit SAT 'le langage obtenu en remplissant les chaînes SAT de longueur n à n g ( n ) . Ensuite:$f$$n^{f(n)}$$g$$g(n)=o(f(n))$$n$$n^{g(n)}$

• SAT 'est en NP (voir ci-dessous!)
• SAT 'n'est pas en P / poly: pour des circuits de taille pour SAT', on obtient des circuits de taille n g ( n ) k pour SAT, mais c'est moins que n f ( n ) pour certains n .$n^k$$n^{g(n)k}$$n^{f(n)}$$n$
• Il n'y a pas de réduction P / poly de SAT à SAT ': supposons par contradiction qu'il existe des circuits de taille n k pour SAT, permettant des portes SAT'. Choisissez N assez grand pour que g ( $C_n$$n^k$$N$et laissern>N. Chaque porte SAT 'enCna au plusnkentrées. En supprimant les entrées de remplissage, nous pouvons découper les portes SAT 'enCnà une porte SAT avec moins de$g(\sqrt{N}) > 2k$$n>N$$C_n$$n^k$$C_n$ entrées, que nous pouvons simuler en utilisantC$\sqrt{n}$ - les portes SAT résultantes ont au plusnk/2entrées. En répétant cela et en traitantCNà la main, SAT aurait des circuits d'environ la tailleO(nknk/2nk/4…)≈O(n2k)qui est inférieur ànf(n)pour certainsn.$C_{\sqrt{n}}$$n^{k/2}$$C_N$$O(n^k n^{k/2} n^{k/4} \dots) \approx O(n^{2k})$$n^{f(n)}$$n$

Modifier:

Le choix de est un peu délicat. Si vous êtes heureux de mettre SAT 'dans la version promise de NP, ce bit n'est pas nécessaire.$g$

Définissez comme étant l'entier maximal de sorte qu'il n'y ait pas de circuit de taille n f ( n ) pour les chaînes de longueur n pour SAT. Définissez g ( n ) par un algorithme qui calcule f ( m ) pour m = 1 , 2 , … et s'arrête après le temps n ou lorsque m = n , et renvoie le plancher de la racine carrée de la valeur la plus élevée trouvée à ce moment. Alors g ( n $f(n)$$n^{f(n)}$$n$$g(n)$$f(m)$$m=1,2,\dots$$n$$m=n$$g(n)$est illimitée et et g ( n ) peut être calculé dans le temps n . Notez maintenant que les arguments ci-dessus reposent uniquement sur SAT n'ayant pas de circuits de taille n f ( n ) pour une infinité de n .$\liminf g(n)/f(n)=0$$g(n)$$n$$n^{f(n)}$$n$

Je trouverais également intéressant de voir une preuve en faisant des trous dans SAT comme dans http://blog.computationalcomplexity.org/media/ladner.pdf . Sans l'exigence NP, cela est assez facile: il existe une séquence telle qu'aucune taille de circuit os ( n k ) k ne détecte les chaînes SAT de longueur n ; restreindre SAT aux chaînes de longueur n 2 2 i pour certains i .$n_1<n_2<\dots$$(n_k)^k$$n$$n_{2^{2^i}}$$i$

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