LETTERS TO THE EDITORS

# Classy Numbers

To the Editors:

In "Unwed Numbers" (*Computing Science,*
January-February 2006), Brian Hayes writes that "Complexity
classes such as NP do not measure the difficulty of any specific
problem instance but rather describe the rate at which difficulty
grows as a function of problem size. If we can solve an
order-*n* Sudoku, how much harder will we have to work to
solve a puzzle of order *n*+1? For problems in NP, the effort
needed grows exponentially." This section contains two subtle errors.

Not only does NP include many easy problems, but we do not yet know for certain how hard its hard ones are. So stating that a problem is in NP doesn’t say much about its difficulty. Although most computer scientists believe that NP includes problems that cannot be solved deterministically in polynomial time, this conjecture has yet to be proven. I suggest that for future descriptions of such hard problems, the term "NP-hard" be used instead of "in NP."

Andrew Koenig

Gillette, NJ

Brian Hayes responds:

As Mr. Koenig (and two other readers) correctly point out, my use of the phrase "in NP" was careless and misleading. I could have made my point more clearly by avoiding altogether the tangled thicket of jargon that surrounds computational complexity theory. I would rephrase the statement as follows: The worst-case difficulty of solving Sudoku puzzles seems to grow exponentially with the size of the puzzle; no subexponential algorithm is known to work in all cases.

EMAIL TO A FRIEND :