4 ms·
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.
by alex_smart 2y ago
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.
- Maxatar 2y agoNo, 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_convention https://en.wikipedia.org/wiki/NP-hardness#NP-naming_conventi...
- deleted 2y ago[deleted]
- alex_smart 2y agoFrom 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
- Maxatar 2y agoYes that is correct for decision problems.