Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.




Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: