# Proof that circuit design problem is NP-hard [closed]

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.

• 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. – jcod0 Sep 23 '15 at 14:07
• 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. – D.W. Sep 23 '15 at 16:42
• 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. – D.W. Sep 23 '15 at 17:16
• 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? – D.W. Sep 23 '15 at 19:01

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.
• 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. – jcod0 Sep 23 '15 at 17:18