4 ms·
This is wrong. NP-hard problems can be solved, they just appear to hard to solve efficiently. NP-hard problems are always decidable, like everything in polyno
by betterunix2 8y ago
This is wrong. NP-hard problems can be solved, they just appear to hard to solve efficiently. NP-hard problems are always decidable, like everything in polynomial hierarchy (P, NP, co-NP, and higher classes that have oracle access to lower classes).
Undecidable problems e.g. the Halting problem cannot generally be solved using an algorithm (so it has to be solved on a case-by-case basis and requires "creativity").
- niklasd 8y agoSorry, but you are flat out wrong. For example, the halting problem is NP-hard and undecidable [1] I think you might confuse NP-hard with NP-complete. There are problems that are NP-hard, not in NP and unsolvable. If a problem is NP-hard _and_ in NP, then they can always be solved. [1] https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness