2-SAT avec XOR-relations NP-complet?
Je me demande s'il existe un algorithme polynomial pour "2-SAT avec relations XOR". Les deux 2-SAT et XOR-SAT sont en P, mais est-ce que sa combinaison? Exemple d'entrée: Partie 2-SAT: (a or !b) and (b or c) and (b or d) Partie XOR: (a xor b xor c xor 1) and (b xor c xor d) En d'autres termes,...