1
$\begingroup$

I have the following problem, and I want to show that it is NP-hard (or NP-complete).

Consider a clause which can have OR and XOR relationship between literals, e.g. $c_1=y_1 \lor y_2 \lor (y_3\oplus y_4)$. Will the assignment of literals such that the equation given by the conjunction of such clauses, e.g. $c_1\wedge c_2 \wedge c_3 \ldots$ is satisfiable or not a problem in NPC or P?

I suspect that the CIRCUIT SAT can be reduced to it, but I am unable to reach there.

$\endgroup$
4
  • $\begingroup$ There is no restriction on the starting problem. I just need to write a formal proof that the problem I am studying is NPC. I first thought that a reduction from 3SAT should be used, but later realised that reduction from CIRC-SAT would be easier. I work in telecommunication sector, this might be trivial for someone from theoretical computer science, but a tutorial styled proof to the problem would be appreciated for a person from my background. $\endgroup$ – jcod0 Sep 23 '15 at 14:07
  • $\begingroup$ Also, please take a look at our reference questions: cs.stackexchange.com/q/9556/755 and cs.stackexchange.com/q/11209/755. I suspect you might find them very helpful. $\endgroup$ – D.W. Sep 23 '15 at 16:42
  • $\begingroup$ Please specify more precisely exactly what form a clause can take. As my answer illustrates, the answer depends heavily on that. Do the $y_i$'s always have to appear positively, or can they be negated (arbitrary literals)? Do you always have to have at least one term of the clause that is just $y_i$? Are you always guaranteed to have exactly one XOR term, and it always involves exactly 2 literals? Please be a lot more precise: a single example is not a specification. $\endgroup$ – D.W. Sep 23 '15 at 17:16
  • $\begingroup$ It's not clear exactly what the set of possible clauses is. The answer will depend critically on these details, but those details aren't specified. Therefore, the question is not answerable as it stands. I'm putting the question on hold to give you a chance to take the time to think through how to specify your problem carefully and then edit the question accordingly. We've already been through a few revisions that each changed the answer, so I want to make sure you have the chance to state the problem you need to solve accurately. e.g., is $y_1 \lor y_2 \lor y_3$ a valid clause? $\endgroup$ – D.W. Sep 23 '15 at 19:01
0
$\begingroup$

If all clauses have the form $y_i \lor y_j \lor (y_k \oplus y_l)$, your problem is in P: simply setting all of the $y_i$ to 1 will satisfy all of the clauses, always. Therefore, it's unlikely to be NP-complete, and you're unlikely to find a reduction from 3SAT (well, unless P=NP).

But if you additionally allow some clauses to take the form $y_i \oplus y_j$, then your problem becomes NP-complete. This follows from Schaefer's dichotomy theorem plus a reduction to double the number of inputs (to enable one to express negated literals); or you can find a direct reduction.

$\endgroup$
5
  • $\begingroup$ Is not the form $y_j\neq y_k$ equivalent to $y_j\oplus y_k$? Because both of them are true (or 1) if $y_j$ and $y_k$ are assigned different values. $\endgroup$ – jcod0 Sep 23 '15 at 17:18
  • $\begingroup$ @jcod0, yes, it's equivalent. This comes down to my comment that you have not specified the problem clearly: you haven't specified clearly what forms a clause can or can't take. $\endgroup$ – D.W. Sep 23 '15 at 17:19
  • $\begingroup$ I realised that the problem can be shown to be NPC using the Schaefer's dichotomy theorem. My problem is a circuit sat problem, in which the equation is given by conjunction of clauses, and each clause is given by XOR and OR operators on literals. $\endgroup$ – jcod0 Sep 24 '15 at 15:14
  • $\begingroup$ @jcod0, I still say the question does not contain a clear statement of the problem. Does each clause have to be an OR of exactly two literals and one XOR, where the XOR is of exactly two literals? Or what? Please edit the question. Note that I've given extensive feedback in the comments under the question on what I find unclear. $\endgroup$ – D.W. Sep 24 '15 at 15:29
  • $\begingroup$ Each clause can have any number of literals, but the operation on the literal can only be OR and XOR. When we have XOR in clause we use brackets as illustrated by some of my earlier example. Thanks. $\endgroup$ – jcod0 Sep 27 '15 at 12:48

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