La complexité de vérifier si deux CNF ont le même nombre de solutions

Étant donné deux CNF, s'ils ont le même nombre d'affectations pour les rendre vraies, répondez "Oui", sinon répondez "Non".

Il est facile de voir que c'est dans , car si nous connaissons le nombre exact de solutions à ces deux CNF, nous les campons simplement et répondons "Oui" ou "Non". $P^{\#P}$

Quelle est la complexité de ce problème?

cc.complexity-theory complexity-classes counting-complexity Mike Chen
la source

Réponses:

Le problème est coNP -hard; vous pouvez facilement réduire le problème UNSAT à ce problème.

Une caractérisation plus précise est que le problème est C ₌ P -complet. En fait, une définition de la classe C ₌ P est que c'est la classe de problèmes qui sont plusieurs fois polynomiaux réductibles à ce problème même (généralement cette définition est exprimée en termes de fonctions GapP ). Mais comme cela ne dit pas grand-chose, permettez-moi de définir cette classe d'une autre manière.

Soit C ₌ P la classe de problèmes qui sont plusieurs fois polynomiaux et réductibles au problème suivant: étant donné un circuit booléen φ et un entier K (en binaire), décider si le nombre d'assignations satisfaisantes de φ est égal à K . Par une réduction standard qui montre l'exhaustivité # P de # 3SAT, nous pouvons restreindre φ à une formule 3CNF sans affecter la classe. La classe C ₌ P contient une classe appelée US , qui contient à la fois UP et coNP.

Avec cette définition, votre problème est C ₌ P-complet. En fait, la dureté C ₌ P est facile à voir d'après la définition de la classe C ₌ P (qui utilise des formules 3CNF).

Pour prouver l'appartenance à C ₌ P, supposons que nous devons décider si deux formules CNF données φ ₁ et φ ₂ ont le même nombre d'assignations satisfaisantes ou non. Sans perte de généralité, nous pouvons supposer que les deux formules ont le même nombre de variables, disons n . Construire un circuit booléen φ qui prend n +1 bits en entrée pour que le nombre d'assignations satisfaisantes de φ soit égal à c ₁ + (2 ⁿ - c ₂ ), où c ₁ et c ₂être le nombre d'assignations satisfaisantes de φ ₁ et φ ₂ , respectivement. Alors le nombre d'assignations satisfaisantes de φ est égal à 2 ⁿ si et seulement si c ₁ = c ₂ .

Tsuyoshi Ito
la source

@Kaveh: Pouvez-vous élaborer?

Tsuyoshi Ito

@Kaveh: Non, ce n'est pas ce que nous voulons. Nous voulons décider si φ_1 et φ_2 ont le même nombre d'assignations satisfaisantes, pas nécessairement le même ensemble d'assignations satisfaisantes.

Tsuyoshi Ito

@Tsuyoshi: D'après votre définition de

, l'IG est-il dans

? Je pense que au moins GI

C_{=} P

$C_=P$

C_{=} P

$C_=P$

\subseteq F P^{C_{=} P}

$\subseteq FP^{C_=P}$

Mike Chen

@Mike: Merci pour le commentaire intéressant. Parlez -vous du résultat de Graph Isomorphism ∈ SPP (Arvind et Kurur 2006 dx.doi.org/10.1016/j.ic.2006.02.002 )? Si oui, vous avez raison; SPP est contenu dans

, de sorte que le graphique isomorphisme ∈

C_{=} P

$\mathrm{C}_=\mathrm{P}$

C_{=} P

$\mathrm{C}_=\mathrm{P}$

Tsuyoshi Ito

@Mike: J'ai appris qu'avant le résultat GraphIso∈SPP, on savait que GraphIso ∈ LWPP : Köbler, Schöning et Torán 1992 . Depuis LWPP ⊆ WPP ⊆

, on n'a pas besoin du résultat plus fort par Arvind et Kurur dire que GraphIso∈

C_{=} P

$\mathrm{C}_=\mathrm{P}$

C_{=} P

$\mathrm{C}_=\mathrm{P}$

Tsuyoshi Ito

Voici une petite variation sur la question d'origine. Soit un oracle qui, en entrée sort 1 si CNF a plus de solutions que CNF . $O$ $(f_1,f_2)$ $f_1$ $f_2$

Compte tenu de cet oracle, nous construisons une machine poly-temps qui peut résoudre le problème # P-complet du calcul du nombre de solutions à un CNF donné . Notez que peut avoir un nombre exponentiel de solutions. $M$ $\varphi$ $\varphi$

fonctionne comme suit: il génère des formules avec un nombre connu de solutions, et en utilisant la recherche binaire et en posant tout au plus des requêtes polynomiales à , il trouve une formule qui ale mêmenombre de solutions que . Il affiche enfin le nombre de solutions qui viennent d'être trouvées. $M$ $O$ $\varphi_i$ $\varphi$

Cela montre que a la complexité #P. $M^O$

MS Dousti
la source

Pardonnez mon ignorance, mais comment générer une formule avec un nombre de solutions prédéfini?

Giorgio Camerani

Soit M un nombre (k + 1) -bit

, et soit

les indices

où

. Faites une formule avec les variables

. Pour chaque

, soit

les sous-formules suivantes: "Tous de

M = \sum_{i = 0}^{k} m_{i} 2^{i}

$M = \sum_{i=0}^k m_i 2^i$

S

$S$

i

$i$

m_{i} = 1

$m_i=1$

x_{0}, \dots, x_{k}

$x_0, \ldots, x_k$

y_{0}, \dots, y_{k}

$y_0, \ldots, y_k$

i \in S

$i \in S$

F_{i}

$F_i$

sont vraies ET parmi

seulement

est vrai. "

affectations satisfaisantes (les variables

sont libres ), et pour

, les affectations satisfaisantes de

sont disjointes en raison de

{x_{0}, \dots, x_{k - i}}

$\{x_0,\ldots,x_{k-i}\}$

{y_{0}, \dots, y_{k}}

$\{y_0, \ldots, y_k\}$

y_{i}

$y_i$

F_{i}

$F_i$

2^{i}

$2^i$

{x_{k - i + 1}, \dots, x_{k}}

$\{x_{k-i+1}, \ldots, x_k\}$

i \neq j

$i\ne j$

F_{i}

$F_i$

F_{j}

$F_j$

y

$y$ variables. La formule

affectations satisfaisantes.

\underset{i \in S}{⋁} F_{i}

$\bigvee_{i\in S} F_i$

M

$M$

mikero

Notez qu'il est PP-complet de décider si, étant donné deux formules CNF f_1 et f_2, f_1 a des affectations plus satisfaisantes que f_2 ou non.

Tsuyoshi Ito

@mikero: Ah, stupide moi! J'aurais dû imaginer ça. Merci pour votre explication éclairante.

Giorgio Camerani

Il semble que c'est au moins NP-difficile car on peut facilement construire une formule SAT avec une seule solution. Ensuite, selon le théorème de Valiant-Vazirani, il y a une réduction probabiliste de chaque formule SAT à un ensemble de problèmes Unique-SAT (déterminer si une formule a une solution unique) et comparer ces problèmes Unique-SAT avec la formule SAT construite avec une seule solution vous permet de déterminer la satisfiabilité de la formule SAT considérée.

Opter
la source

Pour être précis, la première phrase devrait mentionner «sous réductibilité aléatoire» (bien que vous le mentionniez dans la deuxième phrase).

Tsuyoshi Ito