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!EDITTo 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?
MAX-2-XOR-SAT: Why does the special case work?
complexity theory;optimization;satisfiability