Le plus petit circuit booléen pour générer un langage

Considérons un langage non vide de chaînes binaires de longueur n . Je peux décrire L avec un circuit booléen C avec n entrées et une sortie telles que C ( w ) est vrai si w ∈ L : c'est bien connu.$L$$n$$L$$C$$n$$C(w)$$w \in L$

Cependant, je veux représenter avec un circuit booléen C ' avec n sorties et un certain nombre d'entrées, par exemple m , de telle sorte que l'ensemble des valeurs de sortie C ' pour chacune des deux m entrées possibles est exactement L .$L$$C'$$n$ $m$$C'$$2^m$$L$

Étant donné , comment puis-je trouver un tel circuit C ' de taille minimale, et quelle est la complexité? Existe-t-il une relation entre des limites connues concernant la taille des circuits du premier type ( C ) et des circuits de ce second type ( C ′ ), ou la complexité de leur recherche?$L$$C'$$C$$C'$

(Observez qu'il y a une sorte de dualité dans le sens suivant: étant donné , je peux facilement décider si un mot d'entrée w est dans L en évaluant le circuit, mais il est NP-difficile en général de trouver un mot dans L en trouvant une affectation telle que la sortie est vraie. Étant donné C ′, il est également difficile de déterminer si un mot d'entrée w est dans L car je dois voir si une affectation produit w comme sortie, mais il est facile de trouver un mot dans L en évaluant le circuit sur n'importe quelle entrée arbitraire.)$C$$w$$L$$L$$C'$$w$$L$$w$$L$

Je soulignerai une connexion simple à des circuits non déterministes et commenterai brièvement la dureté cryptographique.

Pour , définissez la complexité de l' image, notée i m c ( S ) , comme le nombre minimal de portes dans n'importe quel (fanin-deux, ET / OU / NON) Circuit booléen C : { 0 , 1 } m → { 0 , 1 } n , dont l' image est S . La question porte sur la complexité du calcul i m c ( S ) , étant donné une représentation de S -table de vérité$S \subseteq \{0, 1\}^n$$imc(S)$$C: \{0, 1\}^m \rightarrow \{0, 1\}^n$$S$$imc(S)$$S$(une chaîne de longueur ).$2^n$

Définissez également la complexité du circuit non déterministe de , que nous désignerons n c c ( S ) , comme le plus petit circuit non déterministe C ( x , y ) : { 0 , 1 } n + m ′ → { 0 , 1 } acceptant exactement S . Autrement dit, nous avons besoin de C que x ∈ S ssi ∃ y : C ( $S$$ncc(S)$$C(x, y): \{0, 1\}^{n + m'} \rightarrow \{0, 1\}$$S$$C$$x \in S$ . Il s'agit d'une notion standard, utilisée pour définir la classe non uniforme N P / p o l y : c'est la classe de tous les ensembles S = { S n } n > 0 , avec S n ⊆ { 0 , 1 } n , tel que n c c ( S n ) ≤ p o l y ( n ) .$\exists y: C(x, y) = 1$$NP/poly$$S = \{S_n\}_{n > 0}$$S_n \subseteq \{0, 1\}^n$$ncc(S_n) \leq poly(n)$

Ce que je voulais souligner, c'est que . Les deux directions de cette inégalité sont simples à vérifier. $imc(S) = ncc(S) \pm O(n)$

Soit la complexité du circuit déterministe. En utilisant Razborov-Rudich, l'article que Dai Le mentionne montre (en gros ici) que sous certaines hypothèses cryptographiques, il est difficile de distinguer les tables de vérité de S avec d c c ( S ) petit, des tables de vérité de vraiment aléatoires S (avec d c c ( S ) presque maximal). S aléatoire a également n c c ( S ) presque maximal, et nous avons bien sûr$dcc(S)$$S$$dcc(S)$$S$$dcc(S)$$S$$ncc(S)$ . Votre problème est donc difficile sous les mêmes hypothèses.$ncc(f) \leq dcc(f)$

Quel est le plus difficile à calculer étant donné une table de vérité pour , d c c ( S ) ou n c c ( S ) ? Y a-t-il une réduction de toute façon? Je ne sais pas.$S$$dcc(S)$$ncc(S)$

Vous devriez jeter un œil à cet article de Kabanets et Cai. Je citerai le résumé de l'article:

$f$$s$$f$$s$$\mathsf{P}$$\mathsf{P}/\mathsf{poly}$$\mathsf{NP}$$\mathsf{E}$

$C'$$F:\{0,1\}^m \rightarrow L$$C'_1,C'_2,\ldots,C'_n$$C'_i$$i^{\rm th}$$F$$C'_i$$\{0,1\}^m\rightarrow \{0,1\}$$C'_i$