Caractérisation des formules à lecture unique sur la base binaire complète

15

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.n2o(1)
  • 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.)Ω(n2/Journaln)
Robin Kothari
la source
avez-vous étudié les BDD, les diagrammes de décision binaires ? ne sont-ils pas assez proches en complexité? mais, je n'ai pas vu une référence de spécification sur le subj.
vzn

Réponses:

-2

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)

vzn
la source
2
Merci pour la référence, mais la méthode de Krapchenko ne fonctionne que sur la base de De Morgan (appelée «base standard» dans le livre de Savage). Ma question concerne la base binaire complète.
Robin Kothari
si la méthode Nechiporuks fonctionne sur une base binaire complète et que la méthode fonctionne sur la base De Morgan / standard dans le livre Savages, pourquoi Krapchenkos ne fonctionne-t-il pas également sur les deux? mais Savage convenu n'a pas d'exemple de la base binaire Krapchenko / full.
vzn
1
La base binaire complète est un surensemble de la base De Morgan. Toutes les limites inférieures qui fonctionnent contre la base binaire complète fonctionnent également contre la base De Morgan.
Robin Kothari
ok, très bien, ce qui exclut la méthode Krapchenko fonctionnant sur la base binaire complète? Je soupçonne que la méthode Nechiporuk a probablement été d'abord appliquée à la base de Morgan puis étendue à la base complète, n'est-ce pas? quelles règles cela exclut pour la méthode Krapchenko?
vzn