Formule 3CNF monotone restreinte: comptage des affectations satisfaisantes (à la fois modulo

Considérez une formule monotone 3CNF ayant les deux restrictions supplémentaires suivantes:

• Chaque variable apparaît dans exactement clauses.$2$
• Étant donné clauses, elles partagent au plus 1 variable.$2$$1$

Je voudrais savoir à quel point il est difficile de compter les affectations satisfaisantes d'une telle formule.

Mise à jour 06/04/2013 12:55

J'aimerais également savoir à quel point il est difficile de déterminer la parité du nombre d'assignations satisfaisantes.

Mise à jour 11/04/2013 22:40

Et si, en plus des restrictions décrites ci-dessus, nous introduisons également les deux restrictions suivantes:

• La formule est plane.
• La formule est bipartite.

Mise à jour 16/04/2013 23:00

$3$$\#P$$\oplus P$-Dur, non plus.

Mise à jour 09/06/2013 07:38

$\oplus P$

Dans tout graphique, la parité du nombre de couvre-sommets est égale à la parité du nombre de couvre-arêtes.

$|C|$$\Delta_{|V|} = O_{|V|} - E_{|V|}$$O_{|V|} + E_{|V|}$

$\oplus$$\oplus$

Au moins la deuxième moitié de la question a été réglée.

Votre problème est probablement # P-complet, même si je n'ai pas pu le trouver dans la littérature.

Une autre façon d'énoncer votre problème est "# 3-regular-edge-cover". À partir d'une formule, construisez un graphique dans lequel chaque clause correspond à un sommet et chaque variable correspond à une arête. Puisque la formule est un 3CNF, le graphique est 3-régulier (ou a un degré maximum 3, selon la définition). De plus, le graphique est simple. Une affectation satisfaisante est identique à une couverture de bord.

Voici quelques problèmes liés:

• # 1-Ex3MonoSat est # P-complet . C'est la même chose que votre problème, seule une solution satisfaisante doit satisfaire exactement une variable dans chaque clause.
• Compter le nombre de couvertures de sommets dans les graphes planaires à 3 intervalles est # P-complet .
• Il existe un FPRAS pour la couverture à bord régulier n ° 3 . Cela suggère que les auteurs pensent que le problème est difficile.