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.