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
8
Medium Priority
?
823 Views
Last Modified: 2012-06-27
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
Comment
Question by:Mr_Lee
  • 4
  • 3
8 Comments
 
LVL 85

Expert Comment

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

Author Comment

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

Expert Comment

by:TommySzalapski
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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 

Accepted Solution

by:
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

by:TommySzalapski
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

by:TommySzalapski
ID: 35691314
Did that make any sense?
0
 

Author Comment

by:Mr_Lee
ID: 35691334
Thanks.
0
 

Author Closing Comment

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

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

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

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…

580 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question