3 ms·
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 o
by Maxatar 2y ago
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_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.