http://www.futurama-madhouse.com.ar/grabs/2acv07/2acv07-069.jpg
In the future, we’ll just be able to compare the P book to the NP book and see if they are the same.
Well, I may not be able to prove that P = NP, but I can certainly prove that NP != intractable. NP-Complete problems are very much in the range of solvable, that’s precisely why they are interesting. If the problem were provably intractable, then there would be no point even trying to prove that the class of NP is equivalent to P.
It’s worth noting that a lot of puzzles and brain-teasers are NP complete. A very commonly cited example is that of Minesweeper. Determining if a certain reveal (the squares shown on screen) is consistent with a certain position (where the mines are) is an NP complete problem. There is often a shortcut to this, but not always. Another example is Sudoku. It is very easy to check to see if a Sudoku solution is correct, but actually deciding on that solution takes a great deal of effort. Another example is the construction of a crossword puzzle. The list goes on and on (http://en.wikipedia.org/wiki/List_of_NP-complete_problems).
The human brain is not mathematically stronger than a computer, and yet we are able to solve these sorts of problems. It may take us a very great deal of time due to the possible branches we must explore, but in the end, we can do it. Every NP-Complete problem has a brute-force solution which runs in exponential (or worse) time. Many NP-Complete problems (like Sudoku) actually have dynamic-programming solutions which run in polynomial time (O(n^k) for some constant k) but with polynomial or even exponential space requirements. I’m sure you’ve met people (you may even be one) who can solve Sudoku puzzles as quickly as they can read the grid. 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.
As others have pointed out, a quick trip to Wikipedia (http://en.wikipedia.org/wiki/NP_complete) would have averted this whole situation. Jeff, I really respect you, but you need to post a correction on this one.
You need to do a little more readin’ and a little less postin’ (I suggest cracking open Algorithms by CLRS)
“Poor Joey. Dating crazy people is one thing, but dating crazy people who claim to have proved P=NP is another matter entirely. I know, I know, my track record with P=NP is hardly any better”
The fact that the girl had no idea what she was claiming to have proved diminishes the outrageousness of her claim.
It is more egregious that you claim to know what NP and P = (or !=) NP means…
Jeff, I understand you are a very busy man but there are a lot of online computer science courses.Arent you sick of writing about things you dont know jack shit about? I mean if you remove the xkcd comic and the NP comic , your post will just have worthless comments.
but who wants to eat 7 rounds of mixed fruit? yuk.
P=NP, when N=1
P=NP or not is (currently) unknown and a lot of very smart people have already tried to solve it, over a long period of time … and failed
There is a million dollar prize to anyone who proves (or disproves) it, and it is thought that many other problems could be solved (relatively) easily if P=NP … so either she is the genius of the century and a multimillionaire (and he would have heard that) or she does not understand what P=NP means …
Most of the people talking about NP-Complete don’t seem to know what it means either …
First, problems in NP are computable, so optimal solutions are possible (of course, assuming NP!=P we need to wait long for them).
“long” as in nearly infinite time, hence they are EFFECTIVELY impossible:
“The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible.”
At least, that is my understanding…
It just takes exponentially longer as the input size increases.
Well, right, I was sort of assuming people would know that a problem with n=1 is pretty fast to solve across the board. 
“NP completeness is one of the great unsolved mysteries in computer science; perhaps the best way to illustrate is through this xkcd cartoon”
this cartoon ilustrates simple O(n^2) problem
Thanks Jeff, more incorrect crap on your blog. You might still have a large following, but people who actually understand Computer Science are getting bored by your bad attempts at looking intelligent. Blog about what you know about and can shed new light on instead of blogging about stuff which you are in no position to talk about with authority.
I’m here to watch the commenters pick apart whatever you did wrong this time Jeff. Good luck though. 
@Tim: “Thanks Jeff, more incorrect crap on your blog. You might still have a large following, but people who actually understand Computer Science are getting bored by your bad attempts at looking intelligent. Blog about what you know about and can shed new light on instead of blogging about stuff which you are in no position to talk about with authority.”
I think at this point it is more about generating buzz and page hits. Screwing up comp sci theories is a great way to drive people to his site and generate hits and interest…
Hey Atwood, hers a suggestion for your next article on Godel’s Theorem.
Jeff Atwood on Godel’s Theorem
Godel’s Theorem is one of the greatest theorems in mathematics; perhaps the best way to illustrate is thorugh this xkcd cartoon: http://xkcd.com/468/
The defining characteristic of Godels thoerem is bla bla bla…(Fill your own crap here. Make sure you dont write any concrete mathematical definitions. You should make sure your readers can respond with these lines the next time it comes up in their conversation.
Obligatory Book Citation. You should tell your readers that you know some good books. Read the back cover, glance through the table of contents and the introduction if you have time. You know what - fuck it this time. Just link Kurt Godel’s bio in wikipedia.
Conclusion:[Conclude with a statement that doesnt summarize anything, doesnt contribute anything, and hardly makes sense like “first step is learning enought to know when yourre really screwed”, that line was a gold]
[advertisement]
Following kunjaan’s post (nice, by the way) - I just heard some EE/developer try to explain to some VP/Director type the 4 colored map theorem and proof about an hour ago. He actually did an ok job - explaining how the prof was something of a new concept being computer generated with huge numbers of special cases. I’ll refrain from attempting to butcher it ala Atwood.
Jeff,
Congrats on your blogging success and on SO, but you really ought to stop posting garbage…
Something about jumping a shark comes to mind.
You might end up with high school ASP.net programmers as your only readers and I don’t think advertisers would pay as much for those kind of visitors.
[insert advertisement here]
“P=NP, when N=1”
No, that’s incorrect.
P=NP when N=1 or P=0.
@Joe: I agree with Ted. I also read the excerpt as implying that UBC is a “joke” school.
It would be fair to clarify that she never went to UBC.
We are so over NP Complete. You should be looking at transformational functions and how to ride the google wave.
P=NP is fun if you like pure math. It also represents the boundary of how far you can take math without relying on intuition (which has no place in pure math but often produces answers that would be intractable otherwise). This is what we call creative thinking. Beats drinking from the firehose any day.