什么是NPhard问题
答案:2 悬赏:50 手机版
解决时间 2021-11-24 18:12
- 提问者网友：十年饮冰
- 2021-11-24 13:05
什么是NPhard问题
最佳答案
- 五星知识达人网友：愁杀梦里人
- 2021-11-24 14:37
NP困难(NP-hard,non-deterministic polynomial-time hard)问题是计算复杂性理论中最重要的复杂性类之一。某个问题被称作NP困难，当且仅当存在一个NP完全问题可以在多项式时间图灵归约到这个问题。
因为NP困难问题未必可以在多项式的时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间内的解，NP困难问题依然可能没有多项式时间内的解。因此NP困难问题“至少与NPC问题一样难”。
我好像也没完全懂。。。汗。
因为NP困难问题未必可以在多项式的时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间内的解，NP困难问题依然可能没有多项式时间内的解。因此NP困难问题“至少与NPC问题一样难”。
我好像也没完全懂。。。汗。
全部回答
- 1楼网友：持酒劝斜阳
- 2021-11-24 14:53
不知道啊
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯