1
$\begingroup$

The steps involved in proving that a problem is NP-Complete are fairly straightforward to follow, it's the logic behind why the proof is valid that's really throwing me for a loop. Okay so an easy one: we are showing that 3SAT is NP-Complete. There are 2 things that must be shown. First we show that 3SAT is in NP and then we must show that it is NP-Hard. To show that 3SAT is NP we just show that a given solution can be verified in polynomial time. Now say we show 3SAT is NP-Hard using Circuit SAT. We find a polynomial time reduction from Circuit SAT to 3SAT. Then we show that an arbitrary solution to Circuit SAT gives us a corresponding solution for 3SAT and also show that if we're given the solution to a 3SAT problem that was generated by our polynomial time algorithm that we can also derive the solution to the corresponding Circuit SAT problem. That all seems fairly straightforward, but why does doing this allow us to conclude that 3SAT is NP-Hard and thus is NP-Complete?

$\endgroup$
1
  • 5
    $\begingroup$ Ingredient 3 from Pal's answer ("We know that Circuit Sat is NP-complete") is the crucial bit of information missing in your original reasoning. Of course the natural followup question is then "HOW do we know that Circuit Sat is NP-complete?" If all the proofs you saw of this fact use the same format (reduce it to another known-to-be-NP-complete problem) then I can fully understand that you feel 'thrown into a loop'! The only way to break out of this loop is to find a proof of NP-completeness for one NP-complete problem that is 'direct' and not by reducing to completeness of another one. $\endgroup$
    – Vincent
    Dec 6 '21 at 11:52
7
$\begingroup$
  1. There is no contradiction
  2. NP-hard means that the problem is "harder than" all problems in NP.
  3. We know that Circuit Sat is NP-complete.

We know that Circuit Sat is harder than all problems in NP. If 3SAT is harder than Circuit Sat, then 3SAT must also be "harder than" all problems in NP.

NP-complete is defined as NP membership and NP-hardness. You prove both, hence you've proved NP-completeness.

If you're still uncertain, go back to the definitions of NP and polynomial time reductions.

Check also the reference question What is the definition of P, NP, NP-complete and NP-hard?

$\endgroup$
6
  • $\begingroup$ I guess where I'm being confused is reading Erickson's Algorithms textbook. He states the following: "In other words, to prove that your problem is hard, you need to describe an efficient algorithm to solve a different problem, which you already know is hard, using an hypothetical efficient algorithm for your problem as a black-box subroutine. The essential logic is a proof by contradiction. The reduction implies that if your problem were easy, then the other problem would be easy, which it ain’t.". But couldn't CSAT technically be in P, and then we have no issue? $\endgroup$
    – lamyvista
    Dec 6 '21 at 15:31
  • 4
    $\begingroup$ @lamyvista It's contraposition rather than contradiction. We prove "if SAT is easy, then CSAT is easy", which is the contrapositive of "if CSAT is hard, then SAT is hard". $\endgroup$
    – Stef
    Dec 6 '21 at 15:50
  • 1
    $\begingroup$ @lamyvista We know that CSAT is in NP, and we know that CSAT is NP-hard. We don't know whether CSAT is in P or not (though it is if and only if P = NP). If you're using "easy"' to mean "in P" and "hard" to mean "NP-hard" then you're going to get confused, because one is not the negation of the other. $\endgroup$
    – Stef
    Dec 6 '21 at 15:54
  • $\begingroup$ @Stef But isn't the proof itself using P to mean "easy" and hard to mean "NP-Hard"? Just like in your formulation of the contrapositive. $\endgroup$
    – lamyvista
    Dec 6 '21 at 16:02
  • 1
    $\begingroup$ @lamyvista I shouldn't have used these words, sorry. What we prove really is "SAT is not harder than CSAT", or "CSAT is as easy as SAT", or in more formal terms "given an oracle that solves SAT, then we can use that oracle to solve CSAT". There is no direct reference to "NP-hard" or to "P" or to anything that specific. $\endgroup$
    – Stef
    Dec 6 '21 at 16:04
3
$\begingroup$

What is NP

A problem is in NP if, with a polynomial-length "magically provided" proof string for any given problem instance whose answer is "yes", can verify the answer is "yes". Equivalently, if you make a NDTM that accepts problems whose answer is "yes" in polynomial time. These are equivalent; the "proof string" can be treated as the set of choices the NDTM would take to reach the accept state. The "magically provided" bit because the NDTM tries every path, and if any one path accepts, we record that "proof string". A deterministic turning machine could take the description of the NDTM and the "proof string" and verify that the problem is accepted by the NDTM.

What is NP-hard

A problem is in NP-hard if, given a polynomial time solution for it, you could solve all NP problems in polynomial time. In fact, it means you can "reduce" all NP problems to a problem in your NP-hard problem set in polynomial time. This means map the NP problem to an instance of your NP-hard problem in such a way that a solution to your NP-hard problem gives you the answer to your NP problem.

Now, once you have found one NP-hard problem X, you can "reduce" others to it. A reduction is when you take your problem set Y, and show that any problem in X can be mapped to a problem in Y in polynomial time in such a way that solving the Y problem implies the solution to the X problem.

If we have such a reduction, then any arbitrary NP problem into an X problem, then reduce that to a Y problem, and thus a P-time solution to Y problems is sufficient to solve any arbitrary NP problem in P-time.

What is NP complete

NP complete is when something is both NP-hard and in NP. There are problems that are NP-hard but we know (or strongly suspect) are much harder than NP.

Foundation

Now, almost all of the time when you prove something NP-complete, we reduce it to another problem.

At the base of all of this is some problem we proved to be NP-hard and in NP without reducing it to another problem.

The trick is we can carefully pick such a problem so that the proof is pretty much by definition. We defined membership in NP as either acceptance by an NDTM or by effectively a proof-checker ("certificate verifier" if you don't want to talk about proofs). Proving those two are equivalent isn't that hard.

All we have to do is take some more amenable and show it can solve a sufficiently powerful certificate verifying system in polynomial time.

What you end up with is a web of known NP-complete problems. Some of them are reduced with clever tricks, some of them are cleverly designed to be easy to reduce to. And instead of having to go all the way back to the definition of NP to show something is NP-hard, you can just reduce one of a library of known NP-complete ones to it to pull it off.

$\endgroup$
1
$\begingroup$

Take as given the following:

  • Circuit SAT is NP-Complete (which means it is also NP-Hard)
  • A problem is NP-Hard if and only if, for every problem in NP, there exists a polynomial time algorithm that converts it into the NP-Hard problem. This is the definition of NP-Hard.

Now, in your proof, you demonstrate that there exists a polynomial time algorithm that converts any Circuit SAT problem into a 3SAT problem. Consider the following algorithm:

  1. Start with any problem in NP.
  2. Convert the problem into Circuit SAT in polynomial time. This is guaranteed to be possible because Circuit SAT is known to be NP-Complete.
  3. Use your polynomial time conversion algorithm to convert it from Circuit SAT into a 3SAT problem.

Doing two polynomial time algorithms in sequence takes polynomial time, so this algorithm runs in polynomial time. It also converts any problem in NP into a 3SAT problem. The ability to do that in polynomial time is the definition of NP-Hard, therefore 3SAT is NP-Hard.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.