But this is the good kind of math -- without any of those pesky numbers.
but I do numbers
(not proofs) for fun
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.
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??!!
I know, right? Plans is really one of those "don't know what you've got 'til it's gone" things.
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.
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!
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.
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.
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
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!
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?
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?
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.
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.
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.