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?
Mr_LeeAsked:
Who is Participating?
 
Mr_LeeAuthor 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
 
ozoCommented:
can you transform a 3Sat problem to 4-CNF Sat?
0
 
Mr_LeeAuthor Commented:
You meant "REDUCE"? I think we can, but what is the right way to transform?
0
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
TommySzalapskiCommented:
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
 
TommySzalapskiCommented:
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
 
TommySzalapskiCommented:
Did that make any sense?
0
 
Mr_LeeAuthor Commented:
Thanks.
0
 
Mr_LeeAuthor 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.

All Courses

From novice to tech pro — start learning today.