?

Log in

No account? Create an account
How to set up an NP-completeness proof - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

How to set up an NP-completeness proof [Dec. 15th, 2008|08:02 pm]
Lindsey Kuper
[Tags|]

(Edited to add: See the comments for some other, better approaches to steps 3 and 4.)

We have a B501 final on Wednesday, and I've talked to a few people in our class who are confused about how to set up an NP-completeness reduction proof. There seems to be a lot of misinformation floating around about what gets reduced to what and what gets reduced from what and so on and so forth. So, here's a handy template. I hope it helps someone.

To show that problem NEW-PROBLEM is NP-complete:

  1. Show that NEW-PROBLEM is verifiable in polynomial time. That is, given a supposed solution, you must be able to tell that it's actually a solution in polynomial time.1
  2. Consider some known NP-hard problem, OLD-PROBLEM. Given any instance OLD-INSTANCE of OLD-PROBLEM, show how to construct, in polynomial time, a corresponding instance NEW-INSTANCE of NEW-PROBLEM, such that NEW-INSTANCE satisfies NEW-PROBLEM exactly when OLD-INSTANCE satisfies OLD-PROBLEM.2
  3. Suppose that we knew of a polynomial-time algorithm A for deciding NEW-PROBLEM. If we did, we would now be able to convert any instance of OLD-PROBLEM into an instance of NEW-PROBLEM using our handy construction technique from step 2, and then solve it using A. Therefore, we would have a polynomial-time algorithm for OLD-PROBLEM.
  4. But we already know that OLD-PROBLEM is NP-hard! Therefore, our supposition in step 3 is wrong, and we must not know of a polynomial-time algorithm for deciding NEW-PROBLEM. Since NEW-PROBLEM is both verifiable in polynomial time and reducible to an NP-hard problem, NEW-PROBLEM is NP-complete.

Notice that steps 3 and 4 stay the same, regardless of what you do in step 2. Step 2 is the meat of the proof, and it's the only step that ever really changes. Indeed, after you have a construction and you've shown that it works, something like "OLD-PROBLEM is polynomial-time reducible to NEW-PROBLEM, hence NEW-PROBLEM is NP-complete" will probably suffice for the rest of the proof. Still, I think it's helpful to remember why you're doing a reduction: you're showing that NEW-PROBLEM must be NP-hard, because for it to be otherwise would be a contradiction.

There's no magic way to make step 2 less hard, but if you can memorize what steps 3 and 4 are all about, then with luck, step 2 will drop in neatly, and you won't start freaking out halfway through about whether you're doing the reduction backwards or something.

That's it. Let me know if I've made any mistakes!


  1. This step of the proof is independent of the others, and you could also do it last, but I like to get it out of the way right away.
  2. This is a polynomial-time reduction from OLD-PROBLEM to NEW-PROBLEM.
LinkReply

Comments:
[User Picture]From: jes5199
2008-12-16 03:10 am (UTC)
ugh, math.
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-12-16 03:24 am (UTC)
But this is the good kind of math -- without any of those pesky numbers.
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2008-12-16 03:33 am (UTC)
but I do numbers (not proofs) for fun
(Reply) (Parent) (Thread)
[User Picture]From: pmb
2008-12-16 03:47 am (UTC)
That's exactly it! Hints for tests: When there is 3 of something or something that can be in 3 states, you will generally want to reduce from 3SAT or from 3DPerfectMatching. If something is encodable using a graph, then vertex cover and hamiltonian cycles are the ones to watch out for.
(Reply) (Thread)
[User Picture]From: sonetka
2008-12-16 04:31 am (UTC)
I have only the vaguest idea of what NP-complete means even after A. has explained it to me, but I did wish to say this:

PLANS! AGAIN? WTF??!!
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-12-16 06:07 am (UTC)
I know, right? Plans is really one of those "don't know what you've got 'til it's gone" things.
(Reply) (Parent) (Thread)
[User Picture]From: sonetka
2008-12-16 06:34 am (UTC)
I'm mostly kicking myself for not copying all the email/snail mail addresses on there into a separate file. I've got some, but not enough. Obviously if you're on LJ it's no problem :) - but a lot of people aren't. Damn it. (Am I overreacting a bit? Maybe. I blame nine-month hormones - they're a good scapegoat for most things).

I do wonder what it was about this time - I'd bet good money it had something to do with that whole Sheree Andrews flap.
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2008-12-16 04:31 pm (UTC)
You need addresses, eh? Is it a matter of needing to get large boxes of Christmas cookies mailed out immediately? Because I can give you my home, school, and winter break addresses... *winning smile*

Just kidding. But I mention cookies because I was lying awake last night trying to figure out how to explain the structure of an NP-completeness proof to someone who didn't know what NP-complete meant, and I came up with a analogy involving cookies and cookie recipes. I'll try to write about it once finals are over -- I owe Geek Buffet an update. Also, we're all thinking of you and the nut and wishing you the best!
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-12-16 04:42 am (UTC)
> Given any instance OLD-INSTANCE of OLD-PROBLEM, show how to construct, in polynomial time, a corresponding instance NEW-INSTANCE of NEW-PROBLEM, such that NEW-INSTANCE satisfies NEW-PROBLEM exactly when OLD-INSTANCE satisfies OLD-PROBLEM.

Wait, what? No.

Your terminology of INSTANCE and PROBLEM is a little confusing here. So it may be that you are trying to say the right thing, but your terminology is obscuring the issue.

However the phrase "show how to construct [...] instance NEW-INSTANCE of NEW-PROBLEM" doesn't convey (to me) the correct idea.

Instead of INSTANCE, I would like to use the term algorithm. Because that's really what we're dealing with: algorithms to solve problems. We show that problem π is NP-Hard by showing things about an algorithm α that is used to solve other NP-Hard problems.

And that's the salient point here. For algorithms αi that solve corresponding problems πi, we don't show πq to be NP-Hard by devising an algorithm αq. We show πq to be NP-Hard by devising an algorithm αh to solve another known-NP-hard problem πh such that αh depends on the solution to πq.

Right?

Assume we have a problem πq that I want to test for NP-Hardness. Assume further that we have an oracle Ω = αq that solves πq. Assume finally that we know πh to be NP-Hard. So IF we can come up with an algorithm αh to solve πh that is polytime with the exception of a call to our oracle Ω, THEN we know that we can solve πh in polytime predicate on being able to solve πq in polytime, and πq must then be NP-Hard.

So let us go back to your original terminology. Under my understanding that the term "INSTANCE" is (roughly) synonymous with "ALGORITHM."

> Given any instance NEW-INSTANCE of NEW-PROBLEM, show how to construct, in polynomial time, a corresponding instance OLD-INSTANCE of OLD-PROBLEM, such that OLD-INSTANCE satisfies OLD-PROBLEM exactly when NEW-INSTANCE satisfies NEW-PROBLEM.

See?
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-12-16 06:06 am (UTC)
Actually, I'm not using "instance" as a synonym for "algorithm". Quoting Leivant: "In computation theory the phrase problem is used to refer to a property of discrete objects, such as whether a positive integer is prime. The objects considered are said to be instances of the problem; for example, the instances of the example above are the positive integers. A solution to a problem is an algorithm for deciding which instances of the problem have the property in question. To 'solve' a problem means to design an algorithm that will decide, given its instances, which ones have the property considered." That's the meaning I intend for "instance".

In my step 2, I could have said: "Given any instance NEW-INSTANCE of NEW-PROBLEM, give a polynomial-time algorithm for constructing a corresponding instance..." The algorithm is the method of construction. Sipser would call it a polynomial time mapping reduction. For me, it's a useful way to think about these problems; of course, your way works, too!
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-12-16 06:36 pm (UTC)

I don't believe step 4

I don't believe step 4. Specifically "Therefore, our supposition in step 3 is wrong, and we must not know of a polynomial-time algorithm for deciding NEW-PROBLEM.": how do you get a contradiction without knowing that P is not equal to NP?
(Reply) (Thread)
[User Picture]From: lindseykuper
2008-12-16 08:28 pm (UTC)

Re: I don't believe step 4

Yeah; in steps 3 and 4 I tried to be careful not to say that an algorithm doesn't exist, just that we don't know of one. It's still awkward, though. How would you do it?
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-12-16 10:40 pm (UTC)

Re: I don't believe step 4

The definition of "NEW-PROBLEM is NP-hard" is "for all problems ARBITRARY-PROBLEM in NP, there exists a polynomial time reduction from ARBITRARY-PROBLEM to NEW-PROBLEM" (Sipser, page 253). Note that this definition implies the characterization that you sometimes see (If I can solve NEW-PROBLEM in polynomial time, then for any ARBITRARY-PROBLEM in NP, I can solve ARBITRARY-PROBLEM in polynomial time).

And suppose that we've already shown that OLD-PROBLEM is NP-hard, and that there is a poly-time reduction from OLD-PROBLEM to NEW-PROBLEM. (Your step 2).

We want to show that NEW-PROBLEM is NP-hard. By definition, we want to show: for all problems ARBITRARY-PROBLEM in NP, there exists a polynomial time reduction from ARBITRARY-PROBLEM to NEW-PROBLEM. So assume an ARBITRARY-PROBLEM in NP. Because OLD-PROBLEM is NP-hard, and ARBITRARY-PROBLEM is in NP, there is a poly-time reduction from ARBITRARY-PROBLEM to OLD-PROBLEM. By Step 2, there is a poly-time reduction from OLD-PROBLEM to NEW-PROBLEM. So compose the two reductions, and that gives you a reduction from ARBITRARY-PROBLEM to NEW-PROBLEM.

So steps 3/4 are really just function composition.

I think the confusing thing about this stuff is that there are two preorders on problems that people talk about, one given by polynomial time reductions, and the other given by "if I can solve A, then I can solve B", and they go in opposite direction.

-Dan
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2008-12-17 09:37 pm (UTC)

Re: I don't believe step 4

Function composition! Thanks, that's a lot better. Or, alternatively, we could say more or less the same thing, but in terms of transitivity: "Because OLD-PROBLEM is NP-hard, ARBITRARY PROBLEM ≤P OLD-PROBLEM, and from step 2 we have that OLD-PROBLEM ≤P NEW-PROBLEM. Because ≤P is transitive, ARBITRARY-PROBLEM ≤P NEW-PROBLEM. Therefore NEW-PROBLEM is NP-hard."

That's mathematically sound, unlike what I had before. But I still really want there to be something in there about how, if NEW-PROBLEM were not NP-hard, there would be a giant contradiction that would make the world explode.

I guess I could still use the contradiction idea, but I think I'd need to specify to start out with that OLD-PROBLEM is NP-complete rather than NP-hard. Then I could replace steps 3 and 4 with, "Suppose that NEW-PROBLEM were not NP-hard. Then there would be no NP-complete problem that is poly-time reducible to NEW-PROBLEM. But we just showed that OLD-PROBLEM, which is NP-complete, is poly-time reducible to NEW-PROBLEM. Therefore NEW-PROBLEM is NP-hard." Kind of ugly.
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-12-18 10:15 pm (UTC)

Re: I don't believe step 4

Yes, but that argument basically goes like this: I want to show A. Assume A is false. Now show A directly, without using the assumption that A is false. Therefore we have contradiction. So you might as well use the direct proof of A in the first place, and avoid reasoning classically altogether.
(Reply) (Parent) (Thread)