1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Jul 19, 2017 at 19:08
  • $\begingroup$ @D.W. thanks I've put it into a new question here: cs.stackexchange.com/questions/78110/… $\endgroup$
    – user2998891
    Jul 19, 2017 at 20:00

1 Answer 1

Reset to default
1
$\begingroup$

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.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – user2998891
    Jul 19, 2017 at 17:50
  • $\begingroup$ 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? $\endgroup$
    – user2998891
    Jul 19, 2017 at 17:57
  • $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Jul 19, 2017 at 17:59
  • $\begingroup$ 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. $\endgroup$
    – user2998891
    Jul 19, 2017 at 18:02
  • $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Jul 19, 2017 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.