# NP-Complete

This is a practice problem. I know that Sat, 3Sat is NP-complete. But how to show that 4-CNF Sat is also NP-complete?
###### Who is Participating?

Author Commented:
Let me say if it is correct. For any 3Sat, we can add another variable (literal) to each clause. The truth of each clause will partially base on the truth of the 4th floor, so we can make 3Sat become 4Sat. Right?
0

Commented:
can you transform a 3Sat problem to 4-CNF Sat?
0

Author Commented:
You meant "REDUCE"? I think we can, but what is the right way to transform?
0

Commented:
There is something you can do to turn any generic 3Sat problem into a 4. It's pretty simple so I don't want to just give it away since you will benefit from thinking of it yourself.
0

Commented:
Sort of. You have to keep it so that solving the 4 would also solve the 3 so you need to add something more specific to the 3 so that if the 4 is satisfiable, the 3 is too.
0

Commented:
Did that make any sense?
0

Author Commented:
Thanks.
0

Author Commented:
Mine is a sort of the solution.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.