Quelle est la «plus petite» classe de complexité pour laquelle une borne de circuit superlinéaire est connue?

Toutes mes excuses pour avoir posé une question qui doit sûrement figurer dans de nombreuses références standard. Je suis curieux de savoir exactement la question dans le titre, en particulier je pense aux circuits booléens, sans limite de profondeur. J'ai mis "le plus petit" entre guillemets pour permettre la possibilité qu'il existe plusieurs classes différentes, non connues pour s'inclure les unes les autres, pour lesquelles une borne superlinéaire est connue.

Je pense que les classes les plus petites connues sont $S_2P$ (Cai, 2001), $PP$ (Vinodchandran, 2005) et $(MA \cap coMA)/1$ (Santhanam, 2007). Tous ces facteurs sont en effet connus pour ne pas être dans $SIZE(n^k)$ pour chaque constante $k$ .

Le résultat le plus fort que je connaisse est que pour tout k, il y a un problème dans $S_2^P$ qui nécessite des circuits de taille $\Omega(n^k)$ .

est une classe contenue dans Z P P N P , elle-même contenue dans Σ P 2 ∩ Π P 2 . (Lezoo de la complexitéa plus d'informations sur cette classe.)$S_2^P$$ZPP^{NP}$$\Sigma_2^P \cap \Pi_2^P$

Le résultat découle de la version la plus forte du théorème de Karp-Lipton due à Cai .

Une preuve rapide de la façon dont cela découle du théorème de KL: Premièrement, si SAT nécessite des circuits de taille super-polynomiale, nous avons terminé, car nous avons présenté un problème dans qui nécessite des circuits de taille super-polynomiale. Si SAT a des circuits de taille polynomiale, alors par la version la plus forte du théorème de Karp-Lipton, PH s'effondre en S P 2 . Nous savons que PH contient des problèmes tels problèmes (par le résultat de Kannan), et donc S P 2 contient un tel problème.$S_2^P$$S_2^P$$S_2^P$

Pour les circuits généraux, nous savons qu'il existe des problèmes dans qui nécessitent des circuits de taille Ω ( n k ) , cela est dû à Ravi Kannan (1981) et est basé sur son résultat que P H contient de tels problèmes .$\Sigma^p_2 \cap \Pi^p_2$$\Omega(n^k)$$PH$

Je pense que les meilleures limites inférieures pour sont encore autour de 5 n .$NP$$5n$

Voir le livre d'Arora et Barak, page 297. Richard J. Lipton avait un post sur son blog sur ces résultats, voir aussi celui-ci .

Pour affiner la réponse , pour chaque k ≥ 1 et c , soit * Le problème de recherche 3-SAT n'a pas de circuits ˜ O ( n k ) , soit * Un problème dans O 2 P avec le temps (et la taille du témoin) limité à ˜ O ( n k 2 ) n'a pas de circuits io- O ( n k ( log n ) c ) (io signifie infiniment souvent).$\mathrm{S}_2\mathrm{P}$$k≥1$$c$
$\tilde{O}(n^k)$
$\mathrm{O}_2\mathrm{P}$$\tilde{O}(n^{k^2})$$O(n^k (\log n)^c)$

Si à la place du problème de recherche 3-SAT, nous avons utilisé le problème de décision, temps ~ O ( n k 2 + k ) suffit, et si nous avons utilisé le problème de décision pour le bit i dans l'affectation lexicographique minimale pour 3-SAT , ˜ O ( n min ( k 2 + k , k 3 ) ) suffit.$\mathrm{O}^2\mathrm{P}$$\tilde{O}(n^{k^2+k})$$i$$\tilde{O}(n^{\min(k^2+k,k^3)})$

Un problème de décision non calculable avec les circuits io- est le plus petit nombre N (interrogé à l'aide de ses chiffres binaires) qui n'est pas la table de vérité d'un circuit avec n k ⌊ ( log n ) c + 1 ⌋ portes. Si NP est en P / poly, le problème a un témoin inconscient irréfutable composé des éléments suivants: (1) N (2) un circuit qui, étant donné N ' < N , montre que N ' a un circuit suffisamment petit.$O(n^k (\log n)^c)$$N$$n^k ⌊(\log n)^{c+1}⌋$
$N$
$N' < N$$N'$
(3) (utilisé uniquement pour la borne ) un vérificateur qui nous permet de faire tourner le circuit de l'adversaire pendant (2) seulement O ( 1 ) fois (obtenant 1 bit par course).$\tilde{O}(n^{k^3})$$O(1)$

Sur une note séparée, pour chaque , il y a des problèmes de décision dans (MA ∩ coMA) / 1 qui n'ont pas de circuits O ( n k ) . '/ 1' signifie que la machine reçoit un conseil qui ne dépend que de la taille d'entrée. De plus, la chaîne que Merlin envoie peut être choisie pour ne dépendre que de la taille d'entrée (avec cette restriction, MA est un sous-ensemble de O 2 P ) et de la complexité des conseils Σ P 2 . La preuve (Santhanam 2007) généralise IP = PSPACE et PSPACE⊂P / poly ⇒ PSPACE = MA en utilisant un certain problème complet de PSPACE bien comporté et en remplissant les entrées pour obtenir des tailles de circuit minimales infiniment souvent entre n k + $k$$O(n^k)$$\mathrm{O}_2\mathrm{P}$$Σ_2^P$$n^{k+1}$et , en utilisant des conseils pour détecter suffisamment d'exemples de tels n , et pour ces n , résoudre le problème capitonné en demandant à Merlin de produire un tel circuit.$n^{k+2}$$n$$n$