Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# NP-Complete

Posted on 2011-05-03
Medium Priority
823 Views
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?
0
Question by:Mr_Lee
• 4
• 3

LVL 85

Expert Comment

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

Author Comment

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

LVL 37

Expert Comment

ID: 35691084
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

Accepted Solution

Mr_Lee earned 0 total points
ID: 35691219
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

LVL 37

Assisted Solution

TommySzalapski earned 2000 total points
ID: 35691312
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

LVL 37

Expert Comment

ID: 35691314
Did that make any sense?
0

Author Comment

ID: 35691334
Thanks.
0

Author Closing Comment

ID: 35718439
Mine is a sort of the solution.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
This article will show how Aten was able to supply easy management and control for Artear's video walls and wide range display configurations of their newsroom.
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…
###### Suggested Courses
Course of the Month13 days, 11 hours left to enroll