In article <firstname.lastname@example.org>, Randy <email@example.com> wrote: >Any task that is always solvable (decidable) and whose runtime grows >exponentially with the size of its input set is NP Hard.
No, if the point were just exponential runtime, then one would just stick to the terminology "exponential runtime," and not bother introducing the "NP" terminology.
Informally, NP consists of problems where one can quickly verify the correctness of a solution if the solution is provided. (*Finding* the solution in the first place might take exponential time.) NP-hard problems are those that are "at least as hard" as any problem in NP, where "at least as hard" means that any problem in NP can be reduced to it. -- 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