
Re: On NP Completeness and Intractability
Posted:
Oct 27, 2005 6:00 PM


In article <djr27u$fa$1@joe.rice.edu>, Randy <joe@burgershack.com> wrote: >OK. In lay terms (as the OP requested), why is NP meaningful to >practitioners? What utilitarian subtlety does it capture that >"exponential" does not?
As you mentioned elsewhere, part of your difficulty may be that problems that are beyond NP do not arise in practice as often. However, there is one familiar type of problem that is not (known to be) in NP, namely the playing of strategy games such as chess or go. Depending on exactly how you choose to generalize these games to arbitrarily large boards, they are at least PSPACEcomplete and sometimes EXPcomplete. You can see intuitively that they are not (known to be) in NP, because even if I'm a chessplaying god and can tell you what the best move in any given position is, there's no easy way for you to verify that it's the best move. The chessplaying god could give you a huge table of possibilities as proof, but checking the huge table takes exponential time, rather than polynomial time.
Practically speaking, knowing that there's a difference between playing strategy games and solving NPcomplete problems means that if you have your eye on writing a killer go program that will beat all the competition and sell millions of copies in East Asia, then you will know better than to, say, attempt to formulate the problem as an integer linear program and throw CPLEX at it. Nor will you waste time studying Hochbaum's "Approximation Algorithms for NPHard Problems" or Downey and Fellows's "Parameterized Complexity" even though both books contain much valuable material on algorithms for hard problems.  Tim Chow tchowatalumdotmitdotedu The range of our projectileseven ... the artilleryhowever great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. Galileo, Dialogues Concerning Two New Sciences

