I’m thinking of changing my name. Something catchy like “ochocinco” or 
(pronounced “artist formerly known as Matt”).
The Matt who referred to, “…all the…detractors…”, likely intended his comment to advise against ad hominem statements, and for rational commentary. Either that, or he was himself trolling.
Either way, the subject matter is never advanced by attacking the author, but rather by discussion of the subject. If you cannot discuss a topic rationally, or read silently, then it likely would be best if you left.
We have every right to attack someone who is a clear fake.
““long” as in nearly infinite time, hence they are EFFECTIVELY impossible:”
I wish people wouldn’t say things like “nearly infinite” - it makes no sense.
“Well, right, I was sort of assuming people would know that a problem with n=1 is pretty fast to solve across the board. :)”
I think the problem is you never explain the different ways the problem increases as n increases, which is fundemental to understanding P=NP. Just saying NP-complete problems are effectively impossible to solve, is misleading as it is only true for sufficently large values of n, but then all non-constant problems are impossible to solve for sufficiently large values of n - so this is hardly a defining characteristic.
Moreover, even if you were to just say the defining characteristic of NP-complete is that they have no known polynomial solution,which is what I assume you’re getting at, you would still be wrong as this would apply to problems that are not NP-complete.
@Anonymous: "really? We’re useless because we point out Jeff is (yet again) totally wrong. "
Not at all, you missed my point. I was saying that you can point out that Jeff is wrong in a decent way. Say WHY he’s wrong, and “because” is just not good enough.
It looks to me like half the folks reading this blog are just jealous of it’s success. Sure, Jeff is often wrong, but then, aren’t we all? If you take everything written in this blog as gospel then that’s your problem. Read the blog, comment, and move on - you don’t need to be a pompous dick about.
The original Matt.
@Brian “This isn’t a CS Blog. It’s a programming blog. If you don’t think there is a differance then you’re deluding yourself.”
Which is precisely why this blog is becoming like Swoopo.
“Well, right, I was sort of assuming people would know that a problem with n=1 is pretty fast to solve across the board. :)”
Ah, but you also assumed that people who knew that would assume that you knew that and had assumed that they knew that as well. I assume.
“The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible. Sure, you can approximate a solution, but an optimal solution requires so many calculations as to be infeasible, even with computers that operated at, say … the speed of light.”
Assuming that by “Optimal”, you mean "Extendable (will solve the problem for all potential inputs) and Fast (Within a sensible time-frame); and by “effectively”, you mean “currently”, that’s ALMOST right.
Technically, we may have already found the optimal (means best) solution with “naive search of all possible paths”. It’s just not good enough to be useful. (best doesn’t mean good) Certainly we have the best solutions for certain instances or ranges of the NP-Complete problems. (3-sat’s really easy if you limit the number of valu)
Also, that definition’s not actually defining, as it also applies to all NP problems, and is slightly “more true” for NP-Hard problems, which are at least as hard as NP-Complete problems, and may be completely unsolveable.
NP-Complete is defined thus (I think):
“If we find a solution to one the problems in the NP-Complete set, it will allow us to solve all the problems IN THAT SET in the same time-scale (e.g. Polynomial Time)”
I would appreciate a check from someone else about this. Is there a decent diagram that demonstrates the way the sets fit together in terms of solubility?
I think this one’s right, but I’ve become mistrustful of Wikipedia’s grasp of the NP issue.
http://upload.wikimedia.org/wikipedia/commons/thumb/a/a0/P_np_np-complete_np-hard.svg/800px-P_np_np-complete_np-hard.svg.png
This one is much the same, except it looks older.
http://www.ecst.csuchico.edu/~amk/foo/csci356/notes/ch11/11.2.gif
This one is much the same, except it looks cooler.
http://www.scottaaronson.com/talks/nphard.gif
This one’s way too complicated for this discussion level (P-Complete? Log Space?), but:
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/pic19.gif
On the bright side, merely being willing to TRY to grasp P=NP requires a massive amount of smarts. And attempting to blog about it requires giant brass balls.
"If we find a solution to one the problems in the NP-Complete set, it will allow us to solve all the problems IN THAT SET in the same time-scale (e.g. Polynomial Time)"
Incidentally, this is the part I’m never sure of. If we find an polynomial solution to an NP-Complete problem, does that prove that P==NP, or are there NP problems that are currently not known to be NP-Complete?
Okay, looked up the Cook-Levin theorem. Basically, the principle of that theorem is that because the way that 3-Sat works, if a problem is provably NP, it can be expressed as a 3-Sat problem, and if a problem’s not NP, it can’t be expressed as 3-Sat.
This means that if a polynomial solution to 3-Sat exists, then ALL the NP set is part of P. And that’s NP-Completeness. Wow, I’m back to the same stage of understanding I was at 3 years ago when I did my exams. Kickass.
I don’t know what this weird story about some guy dating a compulsive liar has to do with anything … I’m flummoxed and I’ve never been flummoxed before.
Charles, the story from “the accordian guy” makes for fascinating reading. it was the culmination of dating a crazy woman who lied about everything, but was somehow strangly compelling. For all we know, Joey could have met Esther Reed in one of her many guises. And reading what Reed did, and how she managed to manipulate people around her, well, that’s also worrying.
Jeff, I have a background in Computer Science, good school, master’s degree, the works. And my wife has an Erdos number of 2.
Well, I think this post is great.
These commenters who are bashing you are just petty and bitter. Sometimes it’s very helpful to have a gentle introduction to a technical topic, particularly one where a bit of general knowledge will help people in other contexts.
It’s like saying that a year is 365 days long, except leap years which are 366. A helpful fact! Obviously, to expert astronomers, there’s a whole host of additional technical detail. But a little generalization and approximation for a given audience is good, and should never invite abuse from the experts.
The expo$ure is more imporant than educating peopl.
Was she called Mary Lou Koslowsky ?
http://www.cs.umd.edu/~gasarch/papers/poll.pdf
61. Anonymous3: (Names, schools, dates changed to protect the innocent) On Dec 14, 1991 it
was shown that P=NP by undergraduate Mary Lou Koslowsky on her Algorithms final exam
at The University of Southern North Dakota. Her ingenious but somewhat hastily written
proof, establishing that 3-SAT could be reduced to 2SAT in O(n3) time, received only 2
points of credit out of a possible 25 and the comment “Wrong.” She left computer science
and became a pharmacist, working now at Osco Drugs in Lake Wobogon, where all problems have above average complexity.
The thing that bugs me is that we (programmers) seem to have proved P != NP… judging from all the discussion on how hard NP-complete problems are. Is that any worse than what this girl does?
"Jeff, I have a background in Computer Science, good school, master’s degree, the works. And my wife has an Erdos number of 2.
Well, I think this post is great.
These commenters who are bashing you are just petty and bitter. Sometimes it’s very helpful to have a gentle introduction to a technical topic, particularly one where a bit of general knowledge will help people in other contexts.
It’s like saying that a year is 365 days long, except leap years which are 366. A helpful fact! Obviously, to expert astronomers, there’s a whole host of additional technical detail. But a little generalization and approximation for a given audience is good, and should never invite abuse from the experts."
This is such rubbish. You are arguing from authority and anyone with an Erdos number of 2 should know that that is rubbish. Out of curiousity, where on this list does your wife belong?
https://files.oakland.edu/users/grossman/enp/Erdos2.html
I mean really, what horrible logic. So, because your wife supposeldy has an Erdos number of 2, whatever Jeff says is correct? Really, that’s your argument? That’s just stupid. Try again.
@Charles
"I mean really, what horrible logic. So, because your wife supposeldy has an Erdos number of 2, whatever Jeff says is correct? Really, that’s your argument? That’s just stupid. Try again."
I think his argument is "I am very smart, much smarter than most of the borderline-Asperger’s cases posting here, and as a smart computer scientist I don’t think your post is stupid."
What’s wrong with arguing from authority in this case? Surely your intelligence and understanding of computing is relevant to this discussion?
Well, all it tells me is that the girl tries to impress Joey. If he was dating her she should be reasonably attractive, so why doesn’t he just do her and appreciate what she says, taking it as a compliment.
Think like a topologist(n-spheres) and you can see how the girl knows much more than you.
-“knowledge has been filtered from you read the originals”—
Wow, it’s obvious the girl was just trying to impress Joey, his reaction is the embodiment of geekery. He should just have smiled and given her what she really wanted 