3 ms·
So part of the solution set satisfies P=NP and some satisfy P!=NP?
by sova 9y ago
So 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