Hacker News Reader

To whatever extent the shortest route question is not in NP, it is also not NP-hard.

Both NP and NP-hard are defined for the class of decision problems.

No, NP-Complete is only defined for decision problems. As OP specifically and correctly points out, NP hard applies to decision problems as well as search and optimization problems (and others as well).

You may review the following to clarify the distinction between the various NP complexity classes:

https://en.wikipedia.org/wiki/NP-hardness#NP-naming_conventi...

From the Definition section

>A decision problem H is NP-hard when for every problem L in NP, there is a polynomial-time many-one reduction from L to H

Yes that is correct for decision problems.

Reply on news.ycombinator.com