Taille du circuit pour «au moins n entrées sont vraies»

Dis que tu as $m$ entrées booléennes, et vous êtes donné un seuil $n$. Vous devez construire un circuit booléen qui est évalué à vrai si au moins$n$des entrées vrai. Vous pouvez utiliser les portes ET, OU, NON ou XOR (limité au fan-in two, avec arbitraire fan-out). Asymptotiquement, comment pouvez-vous faire ce circuit?

Toute limite supérieure raisonnablement serrée serait appréciée. Je continue de penser à des façons de construire récursivement un tel circuit mais je ne trouve rien de bon. De plus, tout résultat pour toute autre base raisonnable de portes autorisées serait également utile.

De S. Chaudhuri, J. Radhakrishnan. Restrictions déterministes dans la complexité des circuits :

Théorème 6.1 : Un circuit informatique$T_k^n$ avec $k \leq n^{1/3}$ a $\Omega(k^2(\ln n)/\ln k)$ portes

Où $T_k^n$ est la fonction booléenne qui a la valeur 1 ssi au moins $k$de ses entrées ont la valeur 1 ( fonction seuil ).

Nous pouvons obtenir une sorte de limite supérieure à partir de certaines inclusions de complexité.

$TC^{0}$ est la classe des circuits booléens de taille constante et de taille polynomiale où nous avons également un $MAJORITY$ porte de fan-in illimité, donc il y a une taille $1$ $TC^{0}$ circuit qui calcule la fonction que vous voulez (un $MAJ$ avec toutes les entrées qui y vont).

$NC^{1}$ est la classe des circuits booléens de taille polynomiale et $O(\log n)$profondeur (mais ici nous n'avons que les portes normales). Il est connu que$TC^{0} \subseteq NC^{1}$, donc au pire, vous pouvez calculer $MAJ$ avec une taille poly $O(\log n)$ circuit de profondeur.

Je soupçonne que comme tu as besoin $MAJ$, nous pouvons faire mieux, mais je n'ai pas encore réussi à obtenir une bonne référence. "Introduction à la complexité des circuits" de Vollmer devrait avoir la réduction, mais je n'ai pas de copie disponible. Cela devrait également être une réduction uniforme (c'est-à-dire pour une entrée de taille$n$ nous pouvons produire efficacement le circuit approprié).

Cette question sur cstheory.SE peut également vous être utile, mais elle est assez technique.

avec $T_k^n$ une fonction de seuil standard définie comme dans la réponse de Vors, $T_k^n$est une fonction symétrique. thm 2.11.1 dans Savage [1] donne un$O(n)$ circuit de taille.

[1] Modèles de calcul , John E Savage