P polynomial time - algorithm is fast for small values gets slower as number of cases increases
NP Nondeterministic Polynomial time - algorithm fast for small values gets slower or slower quickly as number of cases increases
NP complete problems are a subset of NP problems that are probably all equivalent and if it could be proven that any one could be solved in polynomial time then all of them could (and so P=NP)
For “sufficiently” small sets all of these are “easy” and for “sufficiently” large sets all of these are “hard” and all are solvable given enough time, it’s just that generally for NP problems it is harder to find an efficient algorithm (it may be impossible if P!=NP)
Jeff - if you’re missing why there’s so much rage from the people with an understanding of NP amongst the comments, I’ve come up with an analogy.
Each time you discuss a topic that you don’t understand without stating that up front, you are making Coding Horror a little bit more like the Swoopo of CS information sources.
In both cases you have the assumption that the [regulatory agencies / readers] won’t dig further and find out that the explanations are shaky.
And it irritates the hell out of people that do understand what’s going on - hell, you were asking people to write to congressfolk about Swoopo.
“Jeff knows “quantity > quality”, and to “always be jabbing”, and… he’s absolutely right. Hence this post = win, as the others before. Just a simple man still doing what he loves, his faith in community and commenters to guide him, even the detractors. Bravo Jeff, bravo, I look forward to every article.”
That’s a very strange attitude. That’s like mindless consumerism. So if you watch a movie, you don’t care what it’s about, who’s in it, the plot, the effects, the cinematography, nothing, just as long as it is really long? If you read a book, does the only thing that matters to you is whether or not it has a lot of pages? Very weird stuff.
Tim and all the other detractors - you realy are a useless bunch of trolls. If you don’t like the blog, don’t read it - you don’t have to be openly hostile to get your point across. If you don’t agree with what Jeff has said, why not say WHY he’s wrong and correct his mistakes, instead of inflating your own ego and clogging up a blog some of us enjoy with worthless comments?
I always find funny when no theoreticians write about P=NP, for example, saying that proving that a problem is NP is almost as difficult as solving the problem is completely false. Actually is quite simple to prove that a problem is in NP. You just have to prove that is in NP (the very easy part) and then that it is NP-Hard
The problem these people are solving is still NP-Complete,
but they are able to hold enough memoized constraints in their
heads as to reduce each sub-problem very efficiently.
Keep in mind that those people are solving a limited part of the problem: in almost all cases, n=9 (though I’ve seen Sudokus with n=6 or n=16).
Extending the problem to n=100 (a 100x100 grid with 100 distinct symbols - which can still be considered small) will really show that Sudoku is NP-Complete: Solving time will go through the roof, but it’s still trivial to check a solution.
These comments are frightening. Who are these psychopaths?
It’s a real shame that Jeff will probably go the route of Nicholas Carr and shut down comments, or be forced out by the same escaped inmates that stopped Kathy Sierra blogging.
Each time you discuss a topic that you don’t understand without stating that up front, you are making Coding Horror a little bit more like the Swoopo of CS information sources.
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.
“If you’re assuming people know stuff, why bother writing the post at all?”
“[…]a problem with n=1 is pretty fast to solve across the board”
Come on, you don’t really think, that anyone has problems with that?
"But you’re never screwed in practice. There’s always a heuristic algorithm or some approximation that is good enough for what you’re trying to do."
Well sometimes you first have to find one, which doesn’t have to be trivial and even if you do it may not fulfill the demands…
@Matt, I don’t see much trolling. All I see is educated people getting annoyed when someone who has a large readership writing about difficult topics in this way. Every time this happens lots of people who might not have a formal CS education learn information that is wrong and wont ever help them. Jeff is doing everyone a disservice with these mostly pointless blog posts, including himself.
Jeff, you are better than this. You used to blog about what you knew deeply about and had passion for. Now I just wonder if you feel you have to blog just to keep your audience happy. Take a look at how Joel Spolsky and Steve Yegge blog. They might not post something for weeks, but when they do they have really thought about it and have written something that people enjoy reading so they keep coming back. They might not tackle hard topics or try to teach something that is just as accessible on Wikipedia, they take a topic they are passionate about and try to shed some new light or new angle on it. They also lay their blog posts out like essays, not broken up with pictures and huge sections of quoted text that is mostly irrelevant. These are the reasons I have respect for them as bloggers, not because they are very clever or know lots, but because they really understand how to blog for an intelligent, educated, technical audience (which I think you want following you).
Recently Steve Yegge stated that he was going to stop blogging and that made me upset because he is a darn good writer. I really don’t know if I would feel anything if you declared you would stop blogging. Just a thought…
“Tim and all the other detractors - you realy are a useless bunch of trolls. If you don’t like the blog, don’t read it - you don’t have to be openly hostile to get your point across. If you don’t agree with what Jeff has said, why not say WHY he’s wrong and correct his mistakes, instead of inflating your own ego and clogging up a blog some of us enjoy with worthless comments?”
really? We’re useless because we point out Jeff is (yet again) totally wrong. I’m leaving. No problem. You can keep the silly posts and believe I’m a troll. The problem is that Jeff is (comically enough) considered a guru on programming - too many people who read this blog will think that what he says is actually true and correct.
I guess content really doesn’t matter. I prefer to read things that are correct. Here’s yet another corner of the internets where truth is not important…
The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible.
There is nothing wrong in that sentence when we consider a large n. When we talk about complexity classes, we always tend to talk about large n! So there is nothing wrong in that sentence as such.
But I do think that this post does not add much value. But we can forgive Jeff for this one time.
Stop bashing Jeff. We will wait for his next post, which will be awesome.
@ Chris Galpin - sorry - my mistake. I should have figured it out from the quotes. I searched and found those articles. That philosophy scares me. I guess it works if all you care about it getting stuff out the door and hoping people will use your stuff and hope that you make lots of money. I guess I’d rather be correct than publish lots of crap. The one thing he misses is that there is only a certain amount of tolerance the market has for garbage - after that threshold you are not viable.
And IMO Jeff has surpassed that limit - at least for me.
And Jeff cashes yet another nice check from the controversy his blog has created.
Look…I don’t know if Jeff is right or wrong, or if the dorks who come in here just to argue (someone on the internet is WRONG!) are right, and I don’t care. If and when I encounter a problem, you can bet that I will do more research into an issue than just read Jeff’s blog.
Jeff gets money from this blog. The more controversy you and he try to stir up, the more ads he serves.
“These comments are frightening. Who are these psychopaths?
It’s a real shame that Jeff will probably go the route of Nicholas Carr and shut down comments, or be forced out by the same escaped inmates that stopped Kathy Sierra blogging.”
He’ll never stop the comments - because that will stop his traffic. And thus his ad revenue.
The post by “Matt” on June 2, 2009 7:16 AM was by a different Matt than the one above. So, hopefully to be clear, the 7:16 AM post and this one was done by Matt (me), and there are other posts by another Matt that aren’t me.
Clear as mud. Only reason I bring it up is because I don’t want people arguing with me or the other Matt and attributing words that we did not write.