Comments: 
But this is the good kind of math  without any of those pesky numbers.
but I do numbers (not proofs) for fun
 From: pmb 20081216 03:47 am (UTC)
 (Link)

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 NPcomplete 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 ninemonth 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 NPcompleteness proof to someone who didn't know what NPcomplete 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!
From: (Anonymous) 20081216 04:42 am (UTC)
 (Link)

> Given any instance OLDINSTANCE of OLDPROBLEM, show how to construct, in polynomial time, a corresponding instance NEWINSTANCE of NEWPROBLEM, such that NEWINSTANCE satisfies NEWPROBLEM exactly when OLDINSTANCE satisfies OLDPROBLEM.
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 NEWINSTANCE of NEWPROBLEM" 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 NPHard by showing things about an algorithm α that is used to solve other NPHard problems.
And that's the salient point here. For algorithms α_{i} that solve corresponding problems π_{i}, we don't show π_{q} to be NPHard by devising an algorithm α_{q}. We show π_{q} to be NPHard by devising an algorithm α_{h} to solve another knownNPhard problem π_{h} such that α_{h} depends on the solution to π_{q}.
Right?
Assume we have a problem π_{q} that I want to test for NPHardness. Assume further that we have an oracle Ω = α_{q} that solves π_{q}. Assume finally that we know π_{h} to be NPHard. 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 NPHard.
So let us go back to your original terminology. Under my understanding that the term "INSTANCE" is (roughly) synonymous with "ALGORITHM."
> Given any instance NEWINSTANCE of NEWPROBLEM, show how to construct, in polynomial time, a corresponding instance OLDINSTANCE of OLDPROBLEM, such that OLDINSTANCE satisfies OLDPROBLEM exactly when NEWINSTANCE satisfies NEWPROBLEM.
See?
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 NEWINSTANCE of NEWPROBLEM, give a polynomialtime 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!
From: (Anonymous) 20081216 06:36 pm (UTC)
I don't believe step 4  (Link)

I don't believe step 4. Specifically "Therefore, our supposition in step 3 is wrong, and we must not know of a polynomialtime algorithm for deciding NEWPROBLEM.": 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?
From: (Anonymous) 20081216 10:40 pm (UTC)
Re: I don't believe step 4  (Link)

The definition of "NEWPROBLEM is NPhard" is "for all problems ARBITRARYPROBLEM in NP, there exists a polynomial time reduction from ARBITRARYPROBLEM to NEWPROBLEM" (Sipser, page 253). Note that this definition implies the characterization that you sometimes see (If I can solve NEWPROBLEM in polynomial time, then for any ARBITRARYPROBLEM in NP, I can solve ARBITRARYPROBLEM in polynomial time).
And suppose that we've already shown that OLDPROBLEM is NPhard, and that there is a polytime reduction from OLDPROBLEM to NEWPROBLEM. (Your step 2).
We want to show that NEWPROBLEM is NPhard. By definition, we want to show: for all problems ARBITRARYPROBLEM in NP, there exists a polynomial time reduction from ARBITRARYPROBLEM to NEWPROBLEM. So assume an ARBITRARYPROBLEM in NP. Because OLDPROBLEM is NPhard, and ARBITRARYPROBLEM is in NP, there is a polytime reduction from ARBITRARYPROBLEM to OLDPROBLEM. By Step 2, there is a polytime reduction from OLDPROBLEM to NEWPROBLEM. So compose the two reductions, and that gives you a reduction from ARBITRARYPROBLEM to NEWPROBLEM.
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
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 OLDPROBLEM is NPhard, ARBITRARY PROBLEM ≤_{P} OLDPROBLEM, and from step 2 we have that OLDPROBLEM ≤_{P} NEWPROBLEM. Because ≤_{P} is transitive, ARBITRARYPROBLEM ≤_{P} NEWPROBLEM. Therefore NEWPROBLEM is NPhard."
That's mathematically sound, unlike what I had before. But I still really want there to be something in there about how, if NEWPROBLEM were not NPhard, 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 OLDPROBLEM is NPcomplete rather than NPhard. Then I could replace steps 3 and 4 with, "Suppose that NEWPROBLEM were not NPhard. Then there would be no NPcomplete problem that is polytime reducible to NEWPROBLEM. But we just showed that OLDPROBLEM, which is NPcomplete, is polytime reducible to NEWPROBLEM. Therefore NEWPROBLEM is NPhard." Kind of ugly.
From: (Anonymous) 20081218 10:15 pm (UTC)
Re: I don't believe step 4  (Link)

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.  