In article <firstname.lastname@example.org>, Randy <email@example.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 PSPACE-complete and sometimes EXP-complete. You can see intuitively that they are not (known to be) in NP, because even if I'm a chess-playing 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 chess-playing 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 NP-complete 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 NP-Hard Problems" or Downey and Fellows's "Parameterized Complexity" even though both books contain much valuable material on algorithms for hard problems. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however 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