Randy 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?
If you have an NP problem of the 'optimizing' sort (such as TSP), there are various search algorithms that can find solutions that are very close to the optimum in a reasonable amount of time.
Also, NP problems are by their very nature eligible for large-scale distributed computing, even across multiple networks.
The same is not necessarily true for all O(exp) problems.
SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT