Is 2-SAT with XOR-relations NP-complete?
-
02-11-2019 - |
Pergunta
I'm wondering if there is a polynomial algorithm for "2-SAT with XOR-relations". Both 2-SAT and XOR-SAT are in P, but is its combination?
Example Input:
2-SAT part:
(a or !b) and (b or c) and (b or d)
XOR part :
(a xor b xor c xor 1) and (b xor c xor d)
In other words, the input is the following boolean formula:
$$(a \lor \neg b) \land (b \lor c) \land (b \lor d) \land (a \oplus b \oplus \neg c) \land (b \oplus c \oplus d).$$
Example Output: Satisfiable: a=1, b=1, c=0, d=0.
Both the number of 2-SAT clauses and the number of XOR clauses in the input are $O(n)$, where $n$ is the number of boolean variables.
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange