https://i.imgur.com/B1IhQiS.jpg
想问一下这题，我的想法是所有NP问题因为都不难于NP-hard问题，所以都可以在p时间内
reduce到NP-hard
而题目说到NP-hard具P时间可解，那是否代表P=NP=NPC=NP-hard呢？还是仅有P=NP=NPC而
已？
谢谢！

我觉得是全部在同一个集合

NP-H可解->NP-C可解-> P = NPNP-C会包含在 P=NP 里" target="_blank" rel="nofollow">

我觉得是这样

Np hard 会在p 但因为定义不会在np(虽然这很怪）https://i.imgur.com/GRbdGsX.jpghttps://i.imgur.com/GRbdGsX.jpg全部问题都可以用p解决 但np hard不能用p验证 所以 npc=np楼上那样画的话np hard就没在p里面了 我这样理解应该没有错吧我想想我应该想错了 npc也是np hard 所以应该是只是跟讲义常出现的那个np=npc=p所以其实题目应该跟 npc有p解 是等价的 可以讨论看看

a大画的好像比较对 我那样画NP-H就不会是P了我的要把NP-H也加进P的范围才行不确定耶 能在P时间解出却不能被验证 感觉也很怪

题目只是说有一个 NP-Hard 问题可以 P 时间解不是说所有 NP-Hard 可以在 P 时间内解所以就只能得到 P = NP = NPP = NP, 而且 P=NP 比 NPC 多两个问题https://goo.gl/shLqO1

抱歉 没看到只说一个 那就是只能得到P=NP