Complexité du circuit de la fonction majoritaire

Soit la fonction majoritaire, c'est-à-dire f ( x ) = 1 si et seulement si ∑ n i = 1 x i > n / 2 . Je me demandais s'il y avait une preuve simple du fait suivant (par «simple», je veux dire ne pas compter sur la méthode probabiliste comme Valiant 84 ou sur les réseaux de tri; fournissant de préférence une construction explicite et directe du circuit):$f: \{0,1\}^n \to \{0,1\}$$f(x) = 1$$\sum_{i = 1}^n x_i > n/2$

peut être calculé par une famille de circuits de O ( log ( n ) $f$$O(\log(n))$ profondeur , de taille poly (n), où les portes se composent de portes NON, de portes OU à 2 entrées et de portes ET à 2 entrées.

La réponse de Kaveh fournit une réponse à la question telle que vous l'avez énoncée (et c'est la preuve habituelle pour montrer que est contenu dans N C 1 ). Mais je pensais que vous auriez pu en fait avoir l'intention de poser une question légèrement différente. À savoir pour un monotone de taille polynomiale explicite$\mathsf{TC}^0$$\mathsf{NC}^1$ formule pour la majorité.

Puisque la majorité est monotone, nous savons qu'elle peut être calculée par une formule monotone. Il existe deux constructions connues de formules monotones de taille polynomiale, à savoir les deux que vous mentionnez, la construction probabiliste de Valiant et la construction via des réseaux de tri. Pour autant que je sache, nous n'avons pas de construction déterministe plus simple que celle fournie par les réseaux de tri.

Lié à cela est également le suivant. Il s'avère que la majorité peut être calculée par des formules qui se composent uniquement de portes (et pas de constantes!). La construction probabiliste de Valiant peut être adaptée pour donner de telles formules de profondeur O ( log ( n ) ) . Cependant, nous ne connaissons ici aucune construction déterministe. En particulier, les réseaux de tri ne conviennent pas pour cela (raison technique: ils fourniraient toutes les fonctions de seuil et seule la fonction majoritaire peut être calculée du tout par des portes M A J 3 ). Il y a cependant des progrès récents sur cette question donnée dans le document$\mathsf{MAJ}_3$$O(\log(n))$$\mathsf{MAJ}_3$ Protocoles multipartites efficaces via des formules de seuil de profondeur de journal par Cohen et al. Ici, ces formules sont construites sur la base d'hypothèses théoriques de complexité ou cryptographiques standard.

Le calcul de la porte à seuil restreint ( ) consiste essentiellement à trier les bits d'entrée.$\sum_i x_i \geq k$

Si vous pouvez trier les bits, il est facile de comparer le résultat à et de calculer le seuil restreint.$k$

En revanche, supposons que nous avons un circuit pour calculer le seuil restreint. Nous pouvons faire une recherche parallèle pour trouver le nombre de ceux dans l'entrée et sortir la liste triée.

$\mathsf{NC^1}$$O(\lg n)$$\mathsf{NC^1}$$O(\lg n)$

Notez qu'il est facile d'implémenter le seuil restreint en utilisant la majorité en ajoutant de nouvelles entrées 1 et 0 à la porte de la majorité.

$\mathsf{AC^0}$. That only shows that majority is in $\mathsf{AC^1}$ and $\mathsf{NC^2}$ since we have unbounded fan-in gates in the binary addition if we do it directly. However it can be done with a bit more work.

We have to use the trick called three-for-two to remain in depth $O(\lg n)$.

three-for-two binary addition:
given three binary numbers $a,b,c$ we can compute two binary numbers $x,y$ such that $a+b+c = x+y$.

Another method is to use signed digit representation of integers where addition can be done in depth $O(1)$ and fan-in 2. (The idea is to use the flexibility that a number can be represented in more than one way to make sure that carries do not propagate).

See section 4 and exercise 4 in

• David Mix Barrington and Alexis Maciel, "Advanced Course on Computational Complexity", lecture 6, IAS/PCMI, 2000.

The proof (due to Miller and Preparata, 1975) that any symmetric function can be computed by circuits over {AND,OR,NOT} in logarithmic depth can be found, e.g., in Complexity of Boolean Functions by Ingo Wegener (Theorem 4.1, page 76). The corresponding circuit has linear size. And since the depth is logarithmic it can be turned to a formula of polynomial size. The proof is elementary and gives an explicit construction. Basically, it shows how to compute the binary representation of the sum of $n$ input bits in logarithmic depth (having this sum it is straightforward to compute majority).

An alternative proof is given by Brodal and Husfeldt: A Communication Complexity Proof that Symmetric Functions have Logarithmic Depth. Again, the proof is elementary and provides an explicit construction.