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
scroll top