热门

最新

红包

立Flag

投票

同城

发布
u010608296
wangchuang2017
3 年前
trueu010608296

问题:如何解决NP问题?

答:一则证明NP等于P，从而从理论上找到NP问题的多项式时间算法；

二则证明NP不等于P，那么就可以归纳得知某些NP问题永远也不可能有多项式时间算法。
评论
点赞
打赏
  • 复制链接
  • 举报
下一条：
问题:论证P！＝NP。答:如果P＝NP，那么每个答案很容易得到验证的问题也同样可以轻松求解。这将对计算机安全构成巨大威胁，目前加密系统的破解就相当于要将一个整数分解为几个因数的乘积，正是其求解过程的繁琐，才能杜绝黑客的入侵。对于有些NP问题，包括因数分解，P≠NP的结果并没有明确表示它们是不能被快速解答的；但对于其子集NP完全问题，却注定了其无法很快得到解决。其中一个著名的例子就是旅行商问题（Travelling Salesman Problem），即寻找从一个城市到另一个城市的最短路线，答案非常容易验证，不过，如果P≠NP，就没有计算机程序可以迅速给出这个答案。作者：wangchuang2022链接：https://www.nowcoder.com/discuss/521361665842053120?sourceSSR=users来源：牛客网