# MAX-2-XOR-SAT: Why does the special case work?

I'm a new user so I cannot respond directly to this post here.

I'm confused about the answers to the question, namely that MAX-2-XOR-SAT is in $P$ iff each clause is of the form $(x_i \oplus \neg x_j)$ (or is it $(x_i \oplus x_j)$? There were two different answers). Couldn't you make a simple substitution $\neg x_i \rightarrow y_i$ such that this is always the case, so that you can get the special case always? For example, you could convert, $(x_1 \oplus \neg x_2) \wedge (x_1 \oplus x_3)$, to $(x_1 \oplus y_2) \wedge (x_1 \oplus x_3)$.

Forgive me if there is something obvious I am missing...I'm new to this field.

Thank you!

EDIT

To clear up confusion, I'm asking if a substitution is made for all clauses with a matching variable. Take for example,

$$(x_1 \oplus x_2) \land (\neg x_1) \land (x_1 \oplus \neg x_3)$$

By substituting $\neg x_3 \rightarrow y_3$ we get:

$$(x_1 \oplus x_2) \land (\neg x_1) \land (x_1 \oplus y_3)$$

Where each 2-clause is of the form $(x_i \oplus x_j)$. It seems that in this case it still remains in $P$. Which raises a new question, how do single clauses affect the complexity of the solution?

• Rather than editing the question to ask new questions or follow-up questions, it's probably better to post a new question via the 'Ask Question' button. Thank you. – D.W. Jul 19 '17 at 19:08
• @D.W. thanks I've put it into a new question here: cs.stackexchange.com/questions/78110/… – user2998891 Jul 19 '17 at 20:00

## 1 Answer

No, you can't make a substitution like that. The resulting formula isn't equivalent to the original formula.

Consider

$$(x_1 \oplus x_2) \land (x_1 \oplus \neg x_2).$$

This formula is not satisfiable. However, if we apply your substitution, we end up with the formula

$$(x_1 \oplus x_2) \land (x_1 \oplus y_2).$$

The resulting formula now has 6 variables and is satisfiable. For example, you can set $x_1=\text{True}$, $x_2=\text{False}$, $y_2=\text{False}$.

The problem is that your substitution doesn't ensure that $y_i = \neg x_i$, so it doesn't preserve satisfiability. (If you wanted to preserve satisfiability, you could do that by making your substitution and then adding clauses of the form $(y_i \oplus x_i)$ ... but while that would preserve satisfiability, it wouldn't preserve the maximum number of clauses that can be simultaneously satisfied, so it still wouldn't help for solving MAX-2-XOR-SAT.)

• Thank you for your response. I think I meant to ask a more complete question. What I'm considering is if all clauses containing a variable are satisfied. For example, in your case, it would be: $$(x_1 \oplus x_2) \land (x_1 \oplus \neg x_2).$$ Which becomes, once $\neg x_2 \rightarrow y_2$, $$(x_1 \oplus \neg y_2) \land (x_1 \oplus y_2).$$ It seems in this case that the satisfiability is preserved. – user2998891 Jul 19 '17 at 17:50
• The case that I'm interested in is more like this: $$(x_1 \oplus x_2) \land (\neg x_1) \land (x_1 \oplus \neg x_3)$$ With the substitution, doesn't this contain only $(x_1 \oplus x_2)$ kind of cases? – user2998891 Jul 19 '17 at 17:57
• @user2998891, perhaps it's worth asking a new question that is clearer about what you are asking. For instance, I'm not sure whether you meant to ask about 2-XOR-SAT or about MAX-2-XOR-SAT. The question you link to is about MAX-2-XOR-SAT, so if you want to know about 2-XOR-SAT, that's a fundamentally different situation. Also, I'm not clear on what substitution you have in mind, or what property you think it has. – D.W. Jul 19 '17 at 17:59
• we are trying to understand whether a certain CNF which encode XOR relationships falls under XOR-SAT or MAX-XOR-SAT, to give you some background. – user2998891 Jul 19 '17 at 18:02
• @user2998891, I don't know what you mean by "falls under". I suggest you think about it hard, then ask a new question where you are clearer about what your question is. – D.W. Jul 19 '17 at 18:05