Tamaño del circuito para "al menos n entradas son verdaderas"

Digamos que tiene entradas booleanas y se le da un umbral . Necesita construir un circuito booleano que se evalúe como verdadero si al menos de las entradas son verdaderas. Puede usar las compuertas AND, OR, NOT o XOR (restringido a fan-in two, con arbitrario fan-out). Asintóticamente, ¿qué tan pequeño puede hacer este circuito?$m$$n$$n$

Cualquier límite superior razonablemente apretado sería apreciado. Sigo pensando en formas de construir recursivamente ese circuito, pero no encuentro nada bueno. Además, cualquier resultado para cualquier otra base razonable de puertas permitidas también sería útil.

De S. Chaudhuri, J. Radhakrishnan. Restricciones deterministas en la complejidad del circuito :

Teorema 6.1 : un circuito de computación$T_k^n$ con $k \leq n^{1/3}$ tiene $\Omega(k^2(\ln n)/\ln k)$ puertas

Dónde $T_k^n$ es la función booleana que tiene el valor 1 iff al menos $k$de sus entradas tienen el valor 1 ( función umbral ).

Podemos obtener algún tipo de límite superior a partir de algunas inclusiones de complejidad.

$TC^{0}$ es la clase de circuitos booleanos de profundidad constante de tamaño polinómico donde también tenemos un $MAJORITY$ puerta de abanico ilimitado, por lo que hay un tamaño $1$ $TC^{0}$ circuito que calcula la función que desea (uno $MAJ$ puerta con todas las entradas que van a ella).

$NC^{1}$ es la clase de circuitos booleanos de tamaño polinómico y $O(\log n)$profundidad (pero aquí solo tenemos las puertas normales). Se sabe que$TC^{0} \subseteq NC^{1}$, en el peor de los casos, puedes calcular $MAJ$ con un tamaño polivinílico $O(\log n)$ circuito de profundidad

Sospecho que solo necesitas $MAJ$, podemos hacerlo mejor, pero todavía no he logrado obtener una buena referencia para esto. La "Introducción a la complejidad del circuito" de Vollmer debería tener la reducción, pero no tengo una copia disponible. También debería ser una reducción uniforme (es decir, para una entrada de tamaño$n$ podemos producir eficientemente el circuito apropiado).

Esta pregunta sobre cstheory.SE también puede tener algo útil para usted, pero es bastante técnica.

con $T_k^n$ una función estándar de umbral definida como en la respuesta de Vors, $T_k^n$Es una función simétrica. thm 2.11.1 en Savage [1] da un$O(n)$ tamaño del circuito

[1] Modelos de computación , John E Savage