MIN-2-XOR-SAT et MAX-2-XOR-SAT: sont-ils NP-durs?

Quelle est la complexité de $\text{MIN-2-XOR-SAT}$ et $\text{MAX-2-XOR-SAT}$ ? Sont-ils en P? Sont-ils durs en NP?

Pour formaliser cela plus précisément,

où $\mathbf{x} = (x_1,\dots,x_m)$ et chaque clause $C_i$ est de la forme $(x_i \oplus x_j)$ ou $(x_i \oplus \neg x_j)$ .

Le problème $\text{2-XOR-SAT}$ est de trouver une affectation à $\mathbf{x}$ qui satisfait $\Phi$ . Ce problème est en $P$ , car il correspond à un système d'équations linéaires mod $2$ .

Le problème $\text{MAX-2-XOR-SAT}$ est de trouver une affectation à $\mathbf{x}$ qui maximise le nombre de clauses satisfaites. Le problème $\text{MIN-2-XOR-SAT}$ est de trouver une affectation à $\mathbf{x}$ qui minimise le nombre de clauses qui sont satisfaites. Quelles sont les complexités de ces problèmes?

Inspiré par MIN ou MAX-True-2-XOR-SAT NP-hard?

Désolé d'avoir répondu à un ancien message

Le problème de déterminer si une instance MONOTONE-2-XOR-SAT (toutes les clauses sont du type ) est satisfaisable peut être réduit au problème de déterminer si un graphe est bipartite, voir ceci .$({x_i}\oplus x_j)$

Pour ce faire, nous créons un graphe avec un nœud pour chaque littéral de la formule et nous connectons chaque littéral à un autre s'ils sont dans la même clause (les bords sont des clauses)$G$

Par exemple:

Si nous avons une formule insatisfaisante qui est $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_3) \wedge({x_2}\oplus x_3) \wedge ({x_1}\oplus x_4)$

Nous avons un graphique comme celui-ci:

ce n'est pas bipartite

Il y a trois clauses qui sont satisfaisables et nous devons donc simplement éliminer un bord

Maintenant, nous pouvons réduire le problème de déterminer si nous pouvons trouver un sous-graphe bipartite maximum avec sommet au problème de déterminer si nous pouvons satisfaire les clauses k dans une formule MONOTONE-MAX-2XOR-SAT, voir ceci . Et le problème de sous-graphique bipartite maximal est équivalent à la coupe maximale$k$$k$

Pour faire la réduction, nous créons simplement un nouveau littéral pour chaque sommet et nous créons une clause pour chaque arête reliant deux littéraux

Par exemple:

Nous avons ce graphique,

$({x_1}\oplus x_2) \wedge ({x_1}\oplus x_4) \wedge({x_2}\oplus x_4) \wedge ({x_2}\oplus x_3) \wedge ({x_4}\oplus x_5) \wedge ({x_3}\oplus x_5)$

$k$$k$

$(x_i\oplus x_j)$$x_i$$x_i\oplus x_j$$x_i\neq x_j$$x_i\oplus x_j$ est vrai si les sommets correspondants ont reçu des couleurs différentes dans le graphique.

Si tous les sommets du graphique peuvent être colorés en utilisant 2 couleurs et qu'aucun des deux sommets avec une part de bord commune n'est affecté de la même couleur, alors l'équation est satisfaisable.

Mais un graphe est bicolore ssi c'est un graphe bipartite. Et déterminer si un graphe est bipartite peut être fait en temps polynomial. Par conséquent, le problème est en P, car si nous pouvons déterminer en temps polynomial que le graphe est un graphe bipartite, il est résoluble, sinon il n'est pas résoluble.