« Core dump | Main | Free (as in beer) speech »

December 12, 2005


Bob Hearn

Well, I have to say that I more or less agree with Dave. The concepts of complexity theory are so far removed from the world of the average reader - even the average science-magazine reader - that we should be satisfied if the flavor of the result is conveyed. To such readers, does it make any difference if the word "NP" is used as a shorthand for "NP-complete"? And while it might be nice to bring in the P vs. NP problem, that's really a whole 'nother topic - the article was about Sudoku, not about the foundations of computer science. Apart from such considerations, the practical meaning of (generalized) Sudoku being NP-complete is that it's hard, and we don't know how to solve it in better than exponential time.

Give the author credit at least for explaining that hardness is not a property of problem instances, but of problem families. Given the presumed space limitations, I'm not sure one could do a whole lot better at communicating the basic meaning of the result. It's hard to write about complexity for a lay audience, even when, unlike most science writers, you're familiar with all the concepts - I've tried. (Except in my case it's generally PSPACE-completeness I'm talking about, which makes it that much harder. Um, so to speak.)

So, yeah - be satisfied that American Scientist is using the letters N and P at all. Any press is good press.


Yeah, but how much harder would it have been (or how much "less understandable by the general public") had Hayes written "...the effort needed is believed to grow exponentially"? (Yes, still not technically correct, but at least it gives readers a better idea...)

It's too bad: I really enjoy Hayes's columns.

he's really not that bad - see also
it's just a confusion between NP and NPC, but explaining the heart
of the matter - asymptotic analysis and exponential growth.

I also liked the fact that he admitted that he does not understand why the Yato and Seta
paper implies hardness for puzzles with unique solution (probably through Valiant-Vazirani, right?).

The conjecture that 3SAT (and so soduko) requires exponential time is very reasonable
given our knowledge.

If you try to be super accurate you'll end up confusing everybody.

Mikey Starfish

Wait, why is any press good press? Does physics *really* benefit from the existence of pop-physics? Or is all that money just going to Random House?

Bob Hearn

Maybe physics doesn't benefit from a lot of pop physics, but computational complexity doesn't have quite the same public awareness. So in this case, any press raises that awareness.

That said, when articles have been written about my results I've taken great pains to make sure the facts are correct, if not necessarily complete.


Yeah, I am also reasonably impressed with the article. The main screweup was confusing NP and NPC. But I presume half of CS ungrads would make the same mistake. After all, what is the difference between Peoples Front of Judea, and Judean Peoples Front ? :)

In my first experience with pop press, the article came out and it contained a quote of "mine" about "flooding meaningful answers with a tsunami of solutions"... After that, I am fine with everything that is written, unless they write that I am a goat (one has to draw the line somewhere).

Dave Bacon

Actually this reminds me of how I distinguish between the physicists and the computer scientists who work in quantum computing: a physicist thinks that NP stands for "not polynomial" and a computer scientist thinks a Hamiltonian is some sort of sandwich.

Did you know that Feynman had to be convinced that the P versus NP problem was an open question!

Interestingly I think I'd have to say that this gaff is not the kind of thing I was thinking about when I was thinking of playing lose with the facts. It's the equivalent in physics of getting Newton's law wrong. There are those in physics who I have seen do the equivalent and I wish, at those moments, to have a big pie to shove in their face.

Just wanted to say that I had heard "P", "NP", "NP-hard" a bunch of times but never sat down and read what they actually meant. Now I know, thanks!

The comments to this entry are closed.