Nombre de portes non xor nécessaires pour implémenter une fonction booléenne N bits

Question

Il y a 2 $ ^ {2 ^ n} $ fonctions possibles qui ont des entrées booléennes $ n $ et une seule sortie booléenne. Certaines de ces fonctions ont des circuits logiques booléens très courts. Certains ont des circuits plus longs.

UN Résultat classique dans la complexité du circuit est que, si vous comptez le nombre total de portes nécessaires pour mettre en œuvre $ f $, la plupart des $ f $ s prennent $ theta (2 ^ n / n) $ 2 à 1 des portes booléennes. Je suis intéressé par une métrique légèrement différente, où Vous pouvez utiliser autant de portes XOR que vous le souhaitez mais vous ne les comptez pas (Idem pour Not Gates, qui ne sont qu'un XOR avec une constante d'entrée). Ainsi, votre circuit pourrait avoir $ n $ et des portes plus 2 $ ^ n $ xor portes, et j'appellerais cela un circuit de $ N $.

J'ai compris qu'il est possible d'implémenter toute fonction $ n $ -Input $ f $ en utilisant au plus 2 $ ^ {n / 2 + 1} $ des portes qui ne sont pas XOR ou non. La stratégie fonctionne en utilisant 2 ^ 2 ^ {n / 2} $ et les portes (avec des portes Xor entrecoupées) pour préparer un ensemble de 2 $ ^ {n / 2} $ bits qui peuvent être xor'd pour faire n'importe quelle fonction de $ n / 2 $ bits. Je prétends ensuite que les bits top $ n / 2 $ du registre de l'indice d'entrée "choisissent" la sous-fonction pour s'appliquer avec les bits $ n / 2 $, et utilisez mes bits d'indicateur pour préparer le 2 ^ {n / 2 } $ SUBLIGNES DE SOUS-FONCTIONS possibles. J'utilise ensuite 2 $ ^ {n / 2} $ et les portes pour le faire la sortie de sous-fonction souhaitée (sélectionnée par les bits $ N / 2 $ du registre d'index d'entrée).

Je suis intéressé à savoir Est-il possible de faire mieux que 2 ^ {n / 2 + 1} $ et les portes, ou est-ce asymptotiquement optimal.