Willem wrote: > 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
Thanks for your civility and your effort, Willem. But since no good deed goes unpunished... :-) I still don't appreciate in a tangible way why the definition of NP isn't equivalent to "exponential". For example, you can linearize either class of problem only by employing an exponentially growing number of parallel processors.
To wit, the solution of 3-SAT or any X^N problem requires exponential runtime (right?). AFAIK, solutions for both classes can be verified in polynomial time. Apparently that doesn't make the latter NP-Hard or NPC, but it sure seems like it makes them equivalent for all practical purposes.
Maybe my difficulty is that I just don't know of any exponential problems that are not NP-Hard or NPC, or whose solutions can't be verified in polynomial time (usually N).