CODEWITHSUNDEEP
algorithmreductionnpcircuitsat
Aivaras Gončarovas
Aivaras Gončarovas

Reputation: 61

Any NP to SAT. How to do that and prove that it is possible?

Let's start here: It is said that all NP problems can be reduced to SAT(boolean satisfiability problem). To be more accurate to Circuit SAT, because all decision problems like NP should end up with answer Yes or No.

But now, if I have a random NP problem, how to build a boolean circuit to test, how to group my input, what kind of gates(AND, NOT, OR etc..) should connect those inputs. So basically, my question how to design boolean Circuit which gives an answer TRUE or FALSE.

Last thing, what that answer means. I understand TRUE as this NP problem can be solved in polynomial time and FALSE cannot, am I correct?

It is huge mess in my mind, don't be really outrageous if I made logical mistakes explaining my question :) I hope you understood it.

Excitingly waiting for answers.

Upvotes: 3

Views: 2569

Answers (1)

Vincent van der Weele
Vincent van der Weele

Reputation: 13177

I understand the confusion but your understanding is not quite how it works.

NP-hardness is a qualification of decision problems, that is, a problem with answer is yes or no. If we want to show that a decision problem is NP-hard, we do so by showing that it is as least as hard as a problem of which we know it is NP-hard already, for instance SAT.

How can we show that problem A is at least as hard as problem B? Well, we can phrase that as

if we can solve A, we can also solve B

So, given an instance of problem B, we convert it to an instance of problem A, use our solution to A to solve it, and convert it back to a solution to B. Assuming that both conversations are easy, we know that A cannot be easier than B, since a solution to A is also a solution to B.

Your understanding thus had it backwards. In order to show that some problem is NP-hard, we to show that it is at least as hard as SAT, that is, given an arbitrary instance of SAT, convert it to an instance of your problem, and then solve that problem. If the answer is "yes", then the original SAT problem was satisfiable, otherwise it wasn't.

Now, as I wrote in a comment, there is no standard way to do the conversion. You somehow need to manipulate your problem, such that it "looks like SAT", in order to make the conversion. For some problems that's easier then others, but I'd claim it's the hardest part of the NP-hardness proof.

What people typically do instead is that they look for another problem, which is known to be NP-hard already, but looks a bit more like their own problem. That way, the reduction becomes a bit easier. But still it requires a lot of work and creativity. I recommend you look at some existing proofs to see how others do this.

Upvotes: 3

Related Questions