American Scientist

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.