Est de trouver une solution à un système d'équations 2SAT séparées par ou (formulaire DNF) dans NP

Question

Je veux savoir si vous trouvez une solution à un nombre spécifique d'équations 2SAT séparées par ou de la porte (formulaire DNF comme ci-dessous) est dans P ou NP.

L'équation comporte des variables totales et chaque clause est une équation de 2SAT en soi dans un sous-ensemble de variables de 1 à n. Exemple:

f= [(x1 || x2) && (! x2 || x3) && (x3 || x4)] ||[(x2 || x5) && (x3 || x6) && (! x4 ||! x6)] ||....

L'équation f est une DNF d'équations de 2SAT, qui a dit des clauses.Vous trouverez une solution à cela dans NP?Si oui comment?

Également, plus particulièrement, je veux aussi savoir si la recherche de fausses instances d'équation f est également dans P ou NP.

Answer 1

• Tout d'abord, laissez-moi noter que le titre de la question est un peu trompeur, car $ p $ est un sous-ensemble de $ Np $ . Voir aussi le commentaire de Yuval Fildus. Je suppose ce que vous destiné à demander est de savoir si c'est dans $ p $ ou dans $ n \ Setminus P $ .
• De plus, le nom "DNF" désigne spécifiquement une disjonction de conjonctions élémentaire , pas une disjonction de fonctions arbitraires. Ce que vous décrivez n'est pas un DNF, mais une disjonction de CNFS.

Avec ça hors du passage, voici ma réponse.

---

1. Pour satisfaire une disjonction de 2-CNFS, tout ce dont vous avez besoin est de satisfaire un d'entre eux. Donc, si vous appliquez l'algorithme à 2 satch vers le premier des CNF et obtenez un «oui», la réponse à tout le problème est «Oui». Sinon, vous passez juste sur le second, et ainsi de suite. Ne devriez pas prendre longtemps, puisque vous n'avez que m d'entre eux. Si aucun d'entre eux ne peut être satisfait individuellement, c'est-à-dire que tous les zéros constants, alors évidemment, tout cela est un zéro constant.

   La réponse à la première partie est la suivante: le problème est dans p, avec l'algorithme de décision suivant:

   Pour chaque 2-CNF, appliquez l'algorithme "normal" 2-SAT (la règle de résolution) pour déterminer s'il est satisfait ou non. Si "oui", revenez simplement "oui". Si vous les traversez tous sans trouver un "oui", revenez "non".

---

2. Maintenant, trouver les "faux" cas de formule (également appelé problème de la tautologie) est une autre question entièrement. Pour une chose, la tautologie des ours d'ARD d'ORS est équivalente à la satisfaction des etrs d'ANDS, de la règle de De Morgan. Mais c'est juste un cas plus général d'un problème de sattement déjà général, n'est-ce pas?

   Considérez ce qui se passe lorsque vous limitez l'ensemble des formules possibles à celles dans lesquelles chaque disjonction à deux éléments n'est vraiment qu'un élément, répété. C'est donc une formule comme $$ F= [(x_1 \ vee x_1) \ & (\ neg x_2 \ vee \ neion x_2) \ & (x_3 \ vee x_3)] \ vee [(x_2 \ vee x_2) \ & (x_4 \ vee x_4) \ & ( x_5 \ vee x_5)] \ Vee ... $$ qui est équivalent à $$ F= [X_1 \ & \ NEG X_2 \ & X_3] \ VEE [x_2 \ & x_4 \ & x_5] \ vee ... $$ qui est juste un DNF normal. Après la transformation de Morgan, vous obtenez un CNF normal, dont la satisfaction est connue pour être dure NP. Par conséquent, tout problème qui inclut celui-ci comme sous-ensemble sera également au moins NP-dur.

   Évidemment, le problème en question ne sera pas extérieur np, car il est toujours vérifiable polynomiquement. Donc, la réponse à votre deuxième question est «dans NP, mais pas dans P».