Contexte
Une formule à lecture unique sur un ensemble de portes (également appelée base) est une formule dans laquelle chaque variable d'entrée apparaît une fois. Les formules à lecture unique sont communément étudiées sur la base de De Morgan (qui a les portes 2 bits ET et OU, et la porte 1 bit NON) et la base binaire complète (qui a toutes les portes 2 bits).
Ainsi, par exemple, le AND de 2 bits peut être écrit comme une formule à lecture unique sur l'une ou l'autre base, mais la parité de 2 bits ne peut pas être écrit comme une formule à lecture unique sur la base de De Morgan.
L'ensemble de toutes les fonctions qui peuvent être écrites sous forme de formule à lecture unique sur la base de De Morgan a une caractérisation combinatoire. Voir, par exemple, Caractérisation combinatoire des formules à lecture unique par M. Karchmer, N. Linial, I. Newman, M. Saks, A. Wigderson.
Question
Existe-t-il une autre caractérisation de l'ensemble des fonctions qui peuvent être calculées par une formule à lecture unique sur la base binaire complète?
Question plus simple (ajoutée dans la v2)
Bien que je sois toujours intéressé par une réponse à la question d'origine, puisque je n'ai reçu aucune réponse, j'ai pensé poser une question plus simple: quelles sont les techniques de limite inférieure qui fonctionnent pour les formules sur la base binaire complète? (Autres que ceux que je liste ci-dessous.)
Notez que maintenant j'essaie de réduire la taille de la formule (= nombre de feuilles). Pour les formules à lecture unique, nous avons la taille de la formule = nombre d'entrées. Donc, si vous pouvez prouver qu'une fonction a besoin d'une formule de taille strictement supérieure à n, cela signifie également qu'elle ne peut pas être représentée comme une formule à lecture unique.
Je connais les techniques suivantes (ainsi qu'une référence pour chaque technique de Boolean Function Complexity: Advances and Frontiers par Stasys Jukna ):
- Méthode de Nechiporuk pour les fonctions universelles (Sec 6.2): Affiche une limite inférieure de taille pour une certaine fonction. Cela ne vous aide pas à trouver des limites inférieures pour une fonction particulière qui pourrait vous intéresser.
- Théorème de Nechiporuk utilisant des sous-fonctions (Sec 6.5): Il s'agit d'une technique de borne inférieure appropriée dans le sens où elle fournira une borne inférieure pour toute fonction qui vous intéresse. Par exemple, elle montre que toute formule sur la base binaire complète qui représente le la fonction de distinction des éléments a la taille . (Et c'est la plus grande borne inférieure que la technique peut prouver - pour n'importe quelle fonction.)
la source
Réponses:
il existe également une méthode appelée la limite inférieure de Krapchenko "qui peut être légèrement plus grande que la méthode Nechiporuks". voir John E Savage, Modèles de calcul, section 9.4.2. (qui est couvert juste après la méthode Nechiporuk dans la section 9.4.1)
la source