Karp, Computational Complexity, and Sudokus

Canâ''t help yourself from doing the occasional Sudoku, despite the mindlessness of all the endless 1-9 number counting and pointless remembering, not to mention the not very interesting logical tricks? Then you might like to know that Richard Karp, a 73-year-old computing theorist at the University of California, Berkeley, has just been awarded one of the 2008 Kyoto Prizes, which this year honor pioneers in information science. The prizes, established by Japanâ''s Inamori Foundation, include a cash gift of 50 million yen and are unusual in that recipients are selected partly on the basis of exceptionally admirable personal traits.

In the 1970s, Karp did foundational work in computational complexity, inventing a way of classifying how susceptible problems are to straight-forward algorithmic procedures. In his schema, as Inamoriâ''s press release says, â''Class P represents problems for which polynomial-time algorithms of deterministic solutions exist; Class NP represents problems for which polynomial-time algorithms of deterministic solutions exist, including the sub-class of NP-Completeâ''the hardest-to-solve problems.â''

As it happens, the humble Sudoko is an example of an NP-Complete problem, as a news story reported in IEEE Spectrum several years ago. In essence, as every Sudoku player will have noticed, though itâ''s extremely easy to verify a Sudoko solution, itâ''s devilishly difficultâ''theoretically impossible, in factâ''to adopt a solving approach that will always work efficiently. Maybe this is what makes the Sudoku so damned seductive.