No, some NP-hard problems are outside NP (i.e. harder than NP), while some are i... | Hacker News

Hacker News new | past | comments | ask | show | jobs | submit

login

dbaupp on Aug 15, 2017 | parent | context | favorite | on: A Solution of the P versus NP Problem?

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

sova on Aug 15, 2017 [–]

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

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact