This is the original problem:And this is 1-in-3-SAT: I am using the 1-in-3-SAT problem (Pc) to reduce from, in order to prove that the original problem (P) is NP-complete. I am stuck at finding a transformation T to prove that Pc <= P, such that every instance X of Pc is transformed into an instance T(X) of P, and runs in polynomial time, and that if the answer to X is YES, so is the answer to T(X), and vice-verso. Same for answer NO.I've found out that if the number of clauses C is more than or equal to the number of variables x, then the answer is always NO. I'm struggling in how to generate (transform) the string a (b) input) from in the P problem. So far, from the options I've tried, the best one has been that I generate the a string by concatenating once every variable x met in all the clauses, but I managed to crack it (prove it wrong), and I'm simply stuck atm.
Need help reducing 1-in-3-SAT to show a problem is NP-complete
np complete;satisfiability;np