4 ms·
Your 2 is the easy part: "NP-hard" is exactly the set of problems to which any NP problems can be reduced in polynomial time, and there are many known existing
by dbaupp 9y ago
Your 2 is the easy part: "NP-hard" is exactly the set of problems to which any NP problems can be reduced in polynomial time, and there are many known existing examples, both within NP (aka NP-complete) and outside it.
- sova 9y agoSo part of the solution set satisfies P=NP and some satisfy P!=NP?
- dbaupp 9y agoNo, some NP-hard problems are outside NP (i.e. harder than NP), while some are inside. The wikipedia article has a good explanation and a good diagram: https://en.wikipedia.org/wiki/NP-hardness https://en.wikipedia.org/wiki/NP-hardness
- sova 9y agoThanks many for your kind explanation. It makes more sense now. I forgot that important detail that mapping is pretty easy as most involvements reduce to and from 3-SAT