Échantillonnage de formules 3-SAT satisfaisantes

Considérons la tâche de calcul suivante: Nous voulons échantillonner une formule 3-SAT de variables (une variante: n variables m clauses) par rapport à la distribution de probabilité uniforme, conditionnée à ce que la formule soit satisfiable:$n$$n$$m$

Q1: Cela peut-il être réalisé efficacement par un ordinateur classique (avec des bits aléatoires)?

Q2: Cela peut-il être réalisé efficacement par un ordinateur quantique?

Je suis également intéressé par les deux variantes suivantes:

V2: Vous échantillonnez toutes les formules par une distribution de probabilité qui donne des formules satisfaisables deux fois le poids des formules non satisfaisantes.

V3: vous échantillonnez où le poids est le nombre d'affectations satisfaisantes (Ici, nous ne nous soucions que du T2).

Mise à jour: la réponse de Colins montre un algorithme simple pour V3. (J'avais tort de supposer que cela est classiquement difficile.) Permettez-moi de mentionner une autre variante des trois questions:

Vous spécifiez à l'avance clauses et vous devez échantillonner des sous-ensembles satisfaisants aléatoires des clauses d'entrée.$m$

Il existe un algorithme simple pour V3. Je vais utiliser la convention qu'il y a clauses possibles, donc 2 8 n 3 formules. (C'est juste pour la simplicité - si vous ne voulez pas que toutes les clauses 8 n 3 soient considérées comme valides, cela n'affecterait pas l'argument suivant.)$(2n)^3$$2^{8n^3}$$8n^3$

$\{0,1\}^n$$7n^3$$1/2$$\phi$$m$$m$$7n^3$