Formule la plus courte pour un CNF monotone à n terme

10

Une formule CNF monotone avec m termes sur n variables ( x1,,xn ) est une formule de la forme , où chaque est un OU d'un sous-ensemble du les variables et vont de à .C i x 1 , , x n i 1 mF(X1,,Xn)=CjeCjeX1,,Xnje1m

Par exemple, est une formule CNF monotone avec 2 termes sur 4 variables.(X1X3X4)(X2X4)

Je recherche la formule la plus courte (pas nécessairement monotone, pas nécessairement CNF, n'importe quelle formule fera l'affaire!) Sur le même ensemble de variables qui représente la même fonction qu'une formule CNF monotone donnée sur n variables avec n termes. (Notez que le nombre de termes et de variables est le même.)

Une façon évidente de construire une formule est d'élargir la définition CNF donnée, ce qui nous donnera une formule de taille . (Définissons la taille d'une formule comme étant la longueur de la formule lorsqu'elle est écrite sous forme de chaîne.) Je veux savoir si c'est la construction générale la plus efficace ou si pour chaque CNF monotone à n termes, il existe une formule de taille .o ( n 2 )O(n2)o(n2)

Je veux juste savoir si c'est possible, je ne suis pas vraiment intéressé par un algorithme. Si ce n'est pas possible, une fonction qui sert de contre-exemple serait formidable. Les pointeurs vers lesquels je peux trouver une réponse dans la littérature sont également appréciés.

EDIT: J'ajoute un exemple pour rendre les choses plus claires.

Supposons que la formule d'entrée soit . Il s'agit d'une formule CNF monotone. Une formule plus courte qui représente la même fonction est la suivante: .x 1( x 2x 3x n )F=(X1X2)(X1X3)(X1Xn)X1(X2X3Xn)

Robin Kothari
la source

Réponses:

11

Vous pouvez obtenir une borne inférieure utilisant un argument de comptage: il existe des CNF e x p ( n 2 ) n -terme sur n variables (c'est facile mais nécessite juste un peu de soin pour s'assurer que il n'y a pas de sur-comptage), mais il existe des formules e x p ( s log s ) (ou même des circuits) de taille au plus s . Ω(n2/Journaln)eXp(n2) nneXp(sJournals)s

Il semble que gagner le dernier facteur sera difficile car il faudrait prouver une limite inférieure quadratique sur la taille de la formule, et je suppose que les quelques techniques existantes pour cela ne suffisent pas. O ( n 2 / log n ) peut même être la bonne réponse - au moins pour la taille du circuit - en utilisant une technique semblable à quatre russes .JournalnO(n2/Journaln)

Noam
la source
Parfait merci! Le facteur log n n'est pas vraiment important pour moi, donc cela répond complètement à ma question.
Robin Kothari
2

Considérez que pour tout CNF, vous pouvez calculer l'ensemble des principaux implicites (dont tout minimum doit être un sous-ensemble) en prenant la fermeture sous résolution et en appliquant l'élimination de la subsomption.

FFF

Bien sûr, je suppose que vous ne voulez pas introduire de nouvelles variables.

nFn

MGwynne
la source
Bien j'aime ça. (En passant, au cas où le cas monotone DNF se présenterait, @Robin, je pense que cela pourrait être intéressant: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.4716 )
Daniel Apon
1
Je ne suis pas sûr de comprendre. La taille CNF minimale peut être la formule CNF monotone que j'ai déjà, mais je recherche la formule de la plus petite longueur. Il n'est pas nécessaire que ce soit CNF ou monotone. Je vais modifier ma question pour que ce soit plus clair.
Robin Kothari
1
Ah, je vois. Eh bien, ce que je disais couvre si cela doit être CNF. S'il peut s'agir d'une formule propositionnelle arbitraire, je dois réfléchir davantage.
MGwynne