Représentation compacte de l'ensemble de solutions d'une instance SAT

Cette question s'est posée dans mon esprit après avoir lu les contributions d'András Salamon et Colin McQuillan à ma question précédente Compter les solutions des formules Monotone-2CNF .

EDIT 30 ^e mars 2011
question n ° 2. Ajouté

EDIT 29 ^e octobre 2010
Question reformulée après proposition András de formaliser à travers la notion de belle représentation d'un ensemble de solution (je l' ai modifié sa notion un peu).

Soit une formule CNF générique à variables. Soit son ensemble de solutions. De toute évidence,peut être exponentielle en . Soitn S | S | n R S $F$$n$$S$$|S|$$n$$R$une représentation de . On dit que est agréable si et seulement si les faits suivants sont tous vrais:$S$$R$

1. $R$ a une taille polynomiale en .$n$
2. $R$ permet d'énumérer les solutions en avec un retard polynomial.$S$
3. | S $R$ permet de détermineren temps polynomial (c'est-à-dire sans énumérer toutes les solutions). $|S|$

Ce serait formidable s'il était possible, en temps polynomial, de construire un tel pour chaque formule.$R$

Des questions:

1. Quelqu'un a-t-il jamais prouvé qu'il existe une famille de formules pour lesquelles une si belle représentation ne peut exister?
2. Quelqu'un a-t-il étudié la relation entre la représentation de et les symétries présentées par ? Intuitivement, les symétries devraient aider à représenter de manière compacte car elles évitent la représentation explicite d'un sous-ensemble de solutions lorsque se résume en fait à une seule solution (c'est-à-dire que de chaque vous pouvez récupérer tous les autres en appliquant une symétrie propre, ainsi chaque est lui-même représentatif de l'ensemble )F S S ′ ⊂ S S ′ s i ∈ S ′ s j ∈ S ′ s i ∈ S ′ S $S$$F$$S$$S' \subset S$$S'$$s_i \in S'$$s_j \in S'$$s_i \in S'$$S'$

Comme indiqué (révision 3), la question a une réponse simple: non.

La raison en est que même pour la classe très restreinte de représentations données par les circuits booléens avec des portes ET, OU et NON, aucune limite inférieure non triviale n'est connue. (De toute évidence, un circuit qui représente représentera également implicitement, et il est facile d'énumérer les solutions en modifiant les entrées du circuit.)$F$$S$

Pour des représentations encore plus restreintes, comme les circuits monotones ou à profondeur constante, les bornes inférieures exponentielles sont connues. Il existe également des bornes inférieures exponentielles pour représenter les formules sous forme CNF ou DNF, bien qu'elles puissent être considérées comme des cas particuliers de circuits à profondeur constante. Enfin, les représentations BDD peuvent être considérées comme des formes compactes de DNF, mais il existe des formules pour lesquelles le BDD nécessite une taille exponentielle pour tout ordre de variable.

Pour rendre votre question plus précise, veuillez considérer la réponse de @ Joshua en détail, et veuillez clarifier ce que vous entendez par «trivial pour énumérer chaque solution unique».

Pour la révision 4, notez la déclaration sur la taille du BDD. Une partie de ce que vous semblez demander est: y a-t-il une représentation plus compacte des formules DNF que des BDD? Soit "BDD a une taille superpolynomiale" signifie "chaque BDD représentant la même fonction que , quel que soit l'ordre des variables, a une taille superpolynomiale", et que "belle représentation" signifie "une représentation qui permet d'énumérer les solutions avec un retard polynomial". Cette question plus spécifique devient alors:$B$$B$

existe-t-il une famille de formules et une belle représentation qui a une taille polynomiale alors que ses BDD ont une taille superpolynomiale?

Est-ce que cela capture l'essence de ce que vous demandez?

[Cette réponse était en réponse à la version antérieure à la révision 6 du 29 octobre 2010.]

Je pense que la question fonctionne plus ou moins maintenant, mais il reste un problème technique. À savoir, comment formaliser "il est trivial d'énumérer chaque solution en regardant simplement une telle structure." Une formalisation peut-être naïve (mais la seule que j'ai pu trouver pour le moment) est la suivante: soit représente la représentation de l'ensemble de solutions de . Pour le moment, je ne mets aucune restriction sur autre que celle où est un CNF sur variables. Ensuite, nous voulons qu'il y ait un algorithme tel que et$R(\varphi)$$S(\varphi)$$\varphi$$R$$|R(\varphi)| \leq poly(n)$$\varphi$$n$$A$$A(R(\varphi)) = S(\varphi)$$A$sur l'entrée s'exécute dans le temps .$R(\varphi))$$poly(n, |S|)$

Sous cette formalisation, les seuls cas difficiles sont ceux où est super-polynomial mais sous-exponentiel. Les autres cas sont traités par la représentation et l'algorithme : si , puis laissez . Si puis laissez . génère simplement et calcule simplement par force brute à partir de . Depuis dans ce dernier cas, cela s'exécute toujours dans le temps .$S$$R$$A$$|S| \leq poly(n)$$R(\varphi) = (0, S)$$|S| \geq 2^{\Omega(n)}$$R(\varphi) = (1, \varphi)$$A(0, S)$$S$$A(1, \varphi)$$S$$\varphi$$|S| = 2^{\Omega(n)}$$O(|S|)$

Cependant, les cas difficiles sont en général impossibles sous cette formalisation. Si de tels et existaient, cela signifierait que la complexité de Kolmogorov liée au temps de chaque était limitée par , ce qui est absurde (puisque presque tous les ensembles ont une complexité maximale de Kolmogorov liée au temps , à savoir ). (Ici est le temps d'exécution de en fonction de .)$R$$A$$p$$S$$poly(n)$$S$$p$$|S|$$p$$A$$|S|$

(Notez que si nous exigeons en outre que s'exécute dans le temps , la réponse à la question est non en général, en supposant : si a une solution unique, alors résoudrait et s'exécuterait dans le temps .p o l y ( n , | φ | ) P ≠ P r o m i s e U P φ A ( R ( φ ) ) φ p o l y ( n $R$$poly(n, |\varphi|)$$P \neq PromiseUP$$\varphi$$A(R(\varphi))$$\varphi$$poly(n)$