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

8

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 moinsndes 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.

ezeidman
la source
4
Vous devez supprimer "..." après les portes et répertorier toutes les portes que vous jugez acceptables. Sinon, vous ne pourrez pas répondre à votre question, par exemple si nous supposons que la porte de seuil (qui est le nom de la porte que vous demandez) est dans la liste, alors la réponse est triviale. Vous devez également indiquer si vous avez des portes de fan-in illimitées ou non.
Kaveh

Réponses:

4

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

TC0 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 TC0 circuit qui calcule la fonction que vous voulez (un MAJ avec toutes les entrées qui y vont).

NC1 est la classe des circuits booléens de taille polynomiale et O(logn)profondeur (mais ici nous n'avons que les portes normales). Il est connu queTC0NC1, donc au pire, vous pouvez calculer MAJ avec une taille poly O(logn) 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 taillen nous pouvons produire efficacement le circuit approprié).

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

Luke Mathieson
la source
0

avec Tkn une fonction de seuil standard définie comme dans la réponse de Vors, Tknest une fonction symétrique. thm 2.11.1 dans Savage [1] donne unO(n) circuit de taille.

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

vzn
la source