A Solution of the P versus NP Problem?

Re:A Solution of the P versus NP Problem? by dbaupp on Monday August 14, 2017 @10:27PM (#15014845)

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.

[ Parent | on HN ]

Re:A Solution of the P versus NP Problem? by sova on Monday August 14, 2017 @10:59PM (#15015011)

So part of the solution set satisfies P=NP and some satisfy P!=NP?

[ Parent | on HN ]

Re:A Solution of the P versus NP Problem? by dbaupp on Monday August 14, 2017 @11:51PM (#15015292)

No, 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

[ Parent | on HN ]

Re:A Solution of the P versus NP Problem? by sova on Tuesday August 15, 2017 @09:59AM (#15018189)

Thanks 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

[ Parent | on HN ]