1
$\begingroup$

I was wondering if the combination of Horn-SAT and XOR-SAT is solvable in polynomial time or not.

It seems they can be solved in polynomial time as both are in class P and also that Horn-SAT is P-complete thus XOR-SAT must be reducible to HORN-SAT .

Just want to clarify if that's the case.

By,HORN-sat with XOR relation I mean a set of clause of the form :

$$ (\neg b \lor\neg d \neg c) \land (a \lor \neg b \lor \neg c) \land (b \oplus c \oplus d).$$ Is the set of clause of the form above solvable in polynomial time?

Reductions exist as shown in this question : https://cstheory.stackexchange.com/q/36704/67865 .

But this post shows that its impossible that such a reuction can exist : https://cstheory.stackexchange.com/q/46088/67865.

that;s why i wanted to clarify if they really can be solved in polynomial time and aren't those two post cotradicting each other?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Please edit your question to define the problem more precisely. It is not clear to me what you mean by the "combination". Please explain how your proposed algorithm would work, and how you'd use the reduction to solve the "combination". $\endgroup$
    – D.W. ♦
    Commented Feb 6, 2023 at 5:51
  • 2
    $\begingroup$ Please don't use "Edit:", and please don't just append more stuff. Instead, revise the question so it reads well for someone who encounters it for the first time, and presents the problem in a logical order. See cs.meta.stackexchange.com/q/657/755. $\endgroup$
    – D.W. ♦
    Commented Feb 6, 2023 at 6:59

1 Answer 1

Reset to default
2
$\begingroup$

Note that we can express variable negation with XOR-clauses, that is, if we have a variable $x$, we can introduce a variable $x'$ and a XOR-clause $(x \oplus x')$, and now $x' = \lnot x$. Therefore, we can write arbitrary CNF:s as conjuctions of clauses with only negative literals and XOR-clauses, and therefore Horn-SAT with XOR-clauses is NP-complete.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ But that means XOR can't be reduced to HORN but isn't HORN P-complete and xor is in class P that means XOR should be reducible to HORN? $\endgroup$
    – Anuj
    Commented Feb 6, 2023 at 9:25
  • $\begingroup$ @Anuj A conjunction of different formulas each of which is in P can make an instance of an NP-hard problem. E.g. 2-CNF and a monotone CNF. $\endgroup$
    – rus9384
    Commented Jul 6, 2023 at 10:11
  • $\begingroup$ A negation of a variable only turns a formula from Horn-CNF to a Horn-renamable CNF, which still is in P. An XOR clause like that does not allow to express arbitrary formulas. $\endgroup$
    – rus9384
    Commented Jul 6, 2023 at 10:18

Your Answer

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

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