programming and human factors
by Jeff Atwood
One of my all time favorite blog entries is a truly epic tale of dating gone wrong that culminates in the strangest reference to P=NP you'll probably ever encounter.
Joey: So you really did graduate from computer engineering?New Girl: Yes I did, from UBC!
Joey: And you took the "Algorithms" course?
New Girl: Of course!
Joey: And you have all the papers you wrote?
New Girl: Yes! I kept them all, and I'll show them to you tomorrow!
Joey: I want to see the one we always called the "Hell Paper" at Queen's -- the mandatory fourth-year paper. You know the one, where we prove P = NP?
New Girl: I did that! I proved P = NP! I placed near the top of the class, and the professor used my paper as an example!
Joey: You proved P = NP?
New Girl: Yes!
Joey: Gotcha.
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. But at least you're not dating me, right?
NP completeness is one of the great unsolved mysteries in computer science; perhaps the best way to illustrate is through this xkcd cartoon:
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.
In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer.
It's doubtful whether anyone will ever prove that P=NP (pdf), but in the meantime it's useful to recognize problems that are NP complete:
Unfortunately, proving inherent intractibility can be just as hard as finding efficient algorithms.The theory of NP-completeness provides many straightforward techniques for proving that a given problem is "just as hard" as a large number of other problems that are widely recognize as being difficult and that have been confounding the experts for years. Armed with these techniques, you might be able to prove that the bandersnatch problem is NP-complete and march into your boss's office and announce:
I can't find an efficient algorithm, but neither can all these famous people.
At the very least, this would inform your boss that it would do no good to fire you and hire another expert on algorithms.
Now you can spend your time looking for efficient algorithms that solve various special cases of the general problem. You might look for algorithms that, though not guaranteed to run quickly, seem likely to do so most of the time. Or you might even relax the problem somewhat, looking for a fast algorithm that merely finds designs that meet most of the component specifications. Thus, the primary application of the theory of NP-completeness is to assist algorithm designers in directing their problem-solving efforts toward those approaches that have the greatest likelihood of leading to useful algorithms.
As with so many things in programming, the first step is learning enough to know when you're really screwed.
Unfortunately for poor Joey, this sad corollary to NP-completeness apparently applies to dating, too.
I also have a feeling (intuition at work) that Jeff is taking some part-time classes to fill the gaps. We will know when we see his first turing machine in the blog post, which is the frankenstein of pure math (and just as lovely).
securityhorror on June 1, 2009 2:00 AMJeff 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.
Christopher Galpin on June 1, 2009 2:02 AM@ Chistopher Galpin: "Jeff knows 'quantity > quality'"
- that is scary. That may work for blogging and advertising, but for the rest of his audience our world has some pretty clear tenets that quality and correctness - they are valued above noise, quantity and "jabbing". You're dead wrong here.
Unless of course you are just talking about blogging and using the readers to generate hit counts and thus ad revenue, in which case we should just boycott the blog as I find that insulting. In any case, I should probably stop wasting my time reading Jeff's blog - it is useless.
tim on June 1, 2009 2:31 AMFor those wanting to try this at home, here's a little solution using Choco (using Groovy):
import static choco.Choco.*
import choco.kernel.model.variables.integer.IntegerVariable
def m = new choco.cp.model.CPModel()
def s = new choco.cp.solver.CPSolver()
def menu = [
'Mixed fruit' : 215,
'French fries' : 275,
'Side salad' : 335,
'Hot wings' : 355,
'Mozzarella sticks' : 420,
'Sampler plate' : 580
]
def vars = new IntegerVariable[menu.size()]
def coeffs = new int[menu.size()]
def sum = 1505
menu.eachWithIndex { k, v, i ->
vars[i] = makeIntVar(k, 0, sum.intdiv(v))
coeffs[i] = v
}
m.addConstraint(eq(scalar(coeffs, vars), sum))
s.read(m)
def more = s.solve()
while (more) {
println "Found a solution:"
vars.each {
def v = s.getVar(it)
if (v.val) println " $v.val * $v.name"
}
more = s.nextSolution()
}
I didn't understand a thing. I haven't done any math courses and I'm a working programmer. I just code all day retrieving shit from the database through some SELECT shit FROM BigPile and load some crap into the database INSERT INTO BigPile(shit) VALUES('lots of shit').
That seems to do the trick. Obviously this kind of programming is too advanced to my boss, so I'm considered somewhat of an expert in my office, (or I think so anyway...).
The last article Jeff did on NP was full of people trying to slowly and carefully explain it to him, with the occasional comment from Jeff that was equivalent to him sticking his head in the sand.
And so after expressing what amounts to willing ignorance on the subject it's interesting to see Jeff climb back into the saddle.
Of course, last time he restated that there's an implicit "I may not know what I'm talking about, this is all a learning exercise for me". Which is really really implicit, considering the writing style strongly suggests otherwise.
There's no Amazon affiliate link to a book he hasn't read this time, so at least he is learning something.
Anyhow, one less thing for my feed reader to check. The more people keep coming back after posts like this, the more posts like this there'll be. I'm living in fear of the day that I have to reeducate people I meet in the workplace who learned their CS theory from here.
First.
Anonymous on June 1, 2009 6:44 AM@Dave, you are absolutely correct. Lot of people who want to learn from these posts will just go home with buzz words, superficial concepts and usually incorrect and misleading statements about the problem. They may be turned off by the subject, maybe wont ask the important questions regarding the subject. People like Jeff Atwood should be ashamed of misusing their clout. Thank God there are people like Michael Sipser, who are genuinely interested in the problem and educating students about it. I dont know if Jeff Atwood even cares about the comments here but linking xkcd, copy pasting from a book, making worthless comments is not just a waste of every body's time but just plain wrong.
kunjaan on June 1, 2009 6:45 AMSecond?
Gotta love math.
JoeMo on June 1, 2009 6:51 AMBah. I proved that P == NP *and* P != NP on Stack Overflow (see 900564).
Jeff Moser on June 1, 2009 6:51 AM1 Mixed Fruit, 2 Hot Wings and a Sampler Plate.
Dave Hemming on June 1, 2009 6:53 AM"The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible."
This is obviously some strange usage of the word "defining" that I hadn't previously been aware of.
Steve W on June 1, 2009 6:58 AMOr seven mixed fruit.
Alex Fountain on June 1, 2009 7:00 AMNP problems can be solved feasibly by a computer as long as the input is sufficiently small
drscroogemcduck on June 1, 2009 7:02 AMThe easiest is still 7 rounds of mixed fruit.
Trevel on June 1, 2009 7:02 AM"The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible."
That doesn't make sense optimal solutions are possible. It just takes exponentially longer as the input size increases.
pete on June 1, 2009 7:06 AMYou made the classic mistake of pasting an xkcd cartoon with the tooltip. The tooltip is part of the fun.
Jeff Lorenzini on June 1, 2009 7:07 AMAre you seriously going to post another thing about P=NP? Really? No, really? 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 on June 1, 2009 7:09 AM"The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible."
Three problems with this:
1) There's no guarantee that a polynomial-time algorithm for an NP-complete problem would require math that we don't know yet.
2) It's not the defining characteristic, since problems in supersets of NP are even more time-consuming.
3) Every problem in NP is computable, so actually, you can find an optimal solution, even if it takes a while.
mkorman on June 1, 2009 7:13 AM@Steve W
I'm not a native Enlish speaker, but I thought it looked OK...
http://en.wiktionary.org/wiki/defining_characteristic
Yeah, but 7 mixed fruit is not a realistic order with just 3 people sitting at the table.
Valid AND practical, is my solution. 1 appetiser each plus the sampler plate for everyone to pick from.
Dave Hemming on June 1, 2009 7:15 AMIn fact, I defy you to find a *better* solution. Maybe I can't prove mine is the optimal solution, but my gut tells me it is.
Dave Hemming on June 1, 2009 7:17 AM>The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible.
No it's not. That's the defining characteristic of non-polynomial time algorithms (Hell, practically speaking, even poly-time algorithms much higher than n^2 are out of our league for large N, but we'll brush that under the carpet).
People seem to treat NP as some kind of synonym for "hard", but what distinguishes NP from other non-polytime algorithms is not how hard they are, but how easy. Or rather how easy it is to check an answer, rather than find it. If you could run every possible guess in paralell, or just happened to pick the right answer first time, you would run in only polynomial time.
Don't why, it reminded me of the sitcom named 'The Big Bang Theory'
Varun Mahajan on June 1, 2009 7:31 AM*sigh* It's articles like this that make people believe that NP means "anything hard" or "unsolvable". NP stands for non-deterministic polynomial time. That means that if anywhere in the algorithm that requires a decision, you can simultaneously follow both paths, the algorithm will find a solution in polynomial time. Math and logic don't really enter into, you simply have to explore an answer space that grows exponentially with problem size. If a problem is NP-complete, there is a provable solution, it just takes exponential time.
NP isn't all hard problems either. If you invented a non-deterministic computer, you could solve NP problems in polynomial time, but there is a class of problems above NP that would still take exponential time. If you find a way to solve those problems quickly, there is yet another class above that, etc. forever.
NP != "hard"
noah on June 1, 2009 7:33 AMThe New Girl should be forced to wear a "Scarlet P=NP" for her sins.
Bob on June 1, 2009 7:34 AMI'll go to lunch with you Dave, 7 rounds of mixed fruit people sounds like it will end in misery and despair. The point of Chotchkies is to express yourself - don't forget the flair!
SteveJ on June 1, 2009 7:37 AMDave Hemming:
For this small of N, you can calculate all solutions quickly. I did. There are just two solutions. Yours and Alex's. May your gut be satisfied :-)
Jeff Moser on June 1, 2009 7:39 AMHey, Jeff, thanks for the link! I'll be at StackOverflow Toronto, so if you need any accordion assistance (perhaps to play off speakers "Keyboard Cat" style), just let me know!
What can I say, it's a crazy world out there, whether you're coding or dating. Just keep your chin up, you wits about you, your accordion tuned, write unit tests and use a condom.
Joey deVilla on June 1, 2009 7:41 AMWow. Jeff just can't resist the NP discussion. It is like watching a train wreck. He is like a moth drawn to a flame.
Jeff: please, stop trying to be a computer scientist, or at least stop trying to explain things you don't understand.
tim on June 1, 2009 7:52 AMAs other already pointed out, the sentence
"The defining characteristic of an NP-complete problem is that optimal solutions, using math and logic as we currently understand them, are effectively impossible."
is obviously wrong.
First, problems in NP are computable, so optimal solutions are possible (of course, assuming NP!=P we need to wait long for them).
For small problem instances it's not a problem even on desktop PCs.
Then, this "definition" does not define the class of NP-complete problems, because anything harder than NPC would still fall under the same description.
And it would be enough to look up Wikipedia to have a simple, understandable explanation:
--- Wikipedia---
In computational complexity theory, the complexity class NP-complete (abbreviated NP-C or NPC, NP standing for Nondeterministic Polynomial time) is a class of problems having two properties:
1) Any given solution to the problem can be verified quickly (in polynomial time); the set of problems with this property is called NP.
2) If the problem can be solved quickly (in polynomial time), then so can every problem in NP.
--- Wikipedia ---
I don't understand the point of writing a post about something the author cannot explain properly...
Kr1s on June 1, 2009 7:52 AMAh, but attendance at UBC implies exposure to atmospheric hallucinogens in much the same way as attendance at Queen's (the engineering department, at least) implies exposure to Gentian violet and at least one visit to the Blue Toucan. I'm sure NG believed she had actually proved P = NP, and that her work was likely confirmed by a sasquatch and a killer whale.
Stan Rogers on June 1, 2009 8:04 AMThe post reminds me of my stupid instructor at the college several months ago. He was talking about P, NP problems and he said some wrong statement that from it you could directly prove that P != NP. I told him what. Are you sure!? He said wait, I'll talk more on that. I said no, it's wrong... He stopped me and said, I'll talk in a minute and you'll understand!!! I said, hey, forget computer science and algorithms for a minute. Just stick to set theory, and proved that if what he said was true, then P != NP, so go and grab your million $ prize. He had nothing to say at the moment and finally agreed he was wrong... Someone helps me out of this stupid college :(
Mehrdad on June 1, 2009 8:28 AMJeff, I think putting UBC and Computer Engineering w/o providing the actual context (that she didn't go there) other than the link in which people may not click, depicted the school and the department as a failed institution. That's a bit unfair.
Ted on June 1, 2009 8:33 AMThe xkcd mouseover doesn't work :(
Dana on June 1, 2009 8:34 AMHeuristic for dating (or how to find a keeper): Date 12 different people at least 3 times each. Make notes on each. Likes, dislikes, points of agreement and friction.
Then go on to new people, and stick with the next one you find that is better than any of the first 12. That's the Keeper.
Ok, I didn't follow that algorithm; I just lucked out.
--
www.chl-tx.com
A famous NP-Complete problem is the one Isaac Asimov presents in his "Foundation" Science-fiction series of novels. The main character tries to find the mathematical expression that defines the behavior of the humanity in order to predict the future. To do that, he would have to study all the societies in the galaxy. Of course that it could take a lot of time, and by the time he get close to the goal, some other societies have already arose or changed.
He compares it to try to shake hands with every living person. It is theoretically possible, but while you are trying, more people are born faster than you can shake hands to everybody.
http://en.wikipedia.org/wiki/Psychohistory_(fictional)
Antonio on June 1, 2009 9:08 AMTed: it it obvious from the excerpt that she didn't study computer science *anywhere*. Nothing unfair there.
Joe on June 1, 2009 9:16 AMWhy did you write this article? What was your purpose? Seriously. Who is your target audience? Dude seriously buy a book and read it rather than ranting about it.
k on June 1, 2009 9:25 AMhttp://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.
David on June 1, 2009 9:41 AMWell, 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.
Daniel Spiewak on June 1, 2009 10:02 AMYou need to do a little more readin' and a little less postin' (I suggest cracking open Algorithms by CLRS)
chris on June 1, 2009 10:02 AM"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...
tim on June 1, 2009 10:15 AMJeff, 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.
cs on June 1, 2009 10:26 AMbut who wants to eat 7 rounds of mixed fruit? yuk.
Alan on June 1, 2009 11:18 AMP=NP, when N=1
Ben S. on June 1, 2009 11:20 AMP=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 ....
Jaster on June 1, 2009 11:39 AM> 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. :)
http://www.codinghorror.com/blog/archives/000957.html
Jeff Atwood on June 1, 2009 11:46 AM"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
Sanmas on June 1, 2009 11:48 AM@Sanmas
I agree. It seems to be a classic linear programming problem.
@Sanmas
I'd really like to see your O(n^2) solution to the 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.
Tim on June 1, 2009 12:35 PMI'm here to watch the commenters pick apart whatever you did wrong _this_ time Jeff. Good luck though. ;)
Christopher Galpin on June 1, 2009 12:39 PM@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...
tim on June 1, 2009 12:40 PMHey 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]
kunjaan on June 1, 2009 1:10 PMFollowing 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]
tim on June 1, 2009 1:23 PM"P=NP, when N=1"
No, that's incorrect.
P=NP when N=1 or P=0.
Santa on June 1, 2009 1:34 PM@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.
Igor Ostrovsky on June 1, 2009 1:40 PMWe 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.
securityhorror on June 1, 2009 1:57 PMP an NP and NP-Complete is not difficult ....!
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)
Jaster on June 2, 2009 2:20 AMJeff - 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.
Dave on June 2, 2009 2:23 AM@tim Quotes were actually shameless insider references to previous entries of certain ideas.
-
*commits seppuku for meta-discussion* (dead now)
Christopher Galpin on June 2, 2009 2:26 AM@Chris Galpin
"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.
Charles on June 2, 2009 2:27 AMTim 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?
Rule #280: Never respond to a critic in writing.
http://rulesformyunbornson.tumblr.com/post/55654369/280-never-respond-to-a-critic-in-writing
how about tax and tip?
waiter on June 2, 2009 2:51 AMI 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
schizoid on June 2, 2009 2:58 AMDaniel Spiewak:
> 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.
Lennaert on June 2, 2009 4:00 AM"Well, right, I was sort of assuming people would know"
If you're assuming people know stuff, why bother writing the post at all?
"the first step is learning enough to know when you're really screwed"
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.
I'm with the others: the NP posts are awful.
Ben on June 2, 2009 4:24 AMThese 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 on June 2, 2009 5:55 AM@Matt,
re:
"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...
Anonymous on June 2, 2009 6:53 AM>>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.
Niyaz PK on June 2, 2009 7:50 AM@ 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.
tim on June 2, 2009 7:59 AMAnd 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.
Who's the idiot now?
Matt on June 2, 2009 8:16 AM"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.
tim on June 2, 2009 8:21 AMThe 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.
Matt on June 2, 2009 8:26 AMI'm thinking of changing my name. Something catchy like "ochocinco" or ☃ (pronounced "artist formerly known as Matt").
MattH on June 2, 2009 10:08 AMThe 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.
Random User 43211 on June 2, 2009 12:07 PMWe have every right to attack someone who is a clear fake.
Random User 2 on June 2, 2009 1:33 PM""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.
Steve W on June 2, 2009 1:38 PM@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.
Matt on June 3, 2009 2:24 AM@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.
Nemo on June 3, 2009 4:12 AM"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.
Tom on June 3, 2009 4:22 AM"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.
Tom on June 3, 2009 5:23 AM> 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.
Peter on June 3, 2009 11:17 AMJeff, 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.
JXG on June 3, 2009 12:37 PMThe expo$ure is more imporant than educating peopl.
@cenbup on June 3, 2009 1:06 PMWas 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?
Semi Essessi on June 7, 2009 2:57 AM@JXG
"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.
Somebod on June 9, 2009 9:45 AMThink 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 :D
andrei on June 12, 2009 6:08 AMAfter reading the original Joey blog post and knowing the whole story, I take that back. I failed at putting it into context.
andrei on June 12, 2009 6:21 AMThe comments to this entry are closed.
Subscribe in a reader
Subscribe via email
|
|
Traffic Stats |
