Ask any molecule what it thinks about the second law of thermodynamics and it will laugh at the question. All the same the molecules, collectively, uphold the second law.
—John Archibald Wheeler, At Home in the Universe, 1994, p. 283.
An amateur’s outlook on computation and mathematics
- Home
-
About
-
Featured
- My God, It’s Full of Dots!
- Counting Your Chickens Before They’re Pecked
- The short arm of coincidence
- Prime After Prime
- Traffic Jams in Javascript
- Sunshine In = Earthshine Out
- Dancing with the Spheres
- The abc game
- Statistical mechanics of magnet balls
- World3, the public beta
- The n-ball game
- A slight discrepancy
- Googling the lexicon
- Kenken-friendly numbers
- Swapping Lies
-
Recent
-
Topics
-
Extras
-
Books
I always thoroughly enjoy reading your articles in American Scientist, and am looking forward to reading your blog!
Speaking of which, probably someone has contacted you regarding a (slight?) mistake in your last column about Sudoku, specifically when you wrote: “For problems in NP, the effort needed grows exponentially.” Of course, the class NP consists of problems whose solutions can be easily verified (this is essentially the definition of NP), but currently we do not know whether all problems in NP can be *solved* efficiently. In any case, problems in NP need not take exponential time (the class of efficiently solvable problems is a subset of NP), and even some of the “hardest” problems in NP (i.e., NP-complete problems) can be solved in sub-exponential (but super-polynomial) time.