admin 管理员组

文章数量: 1086866

P、NP、NPC概念总结

p问题：若存在一个算法，能够在多项式时间内解决问题A，那么问题A为P问题；

NP问题：可以在多项式时间内验证一个解的问题（问题A是NP问题：找到一个算法在多项式时间内求解问题A很困难，但是给定一个解，可以在多项式时间内验证是不是问题A的真实解。）

NPC问题：是NP问题，并且所有的问题都能规约成它。假设问题A是NPC问题，若能够在多项式时间内解决问题A，那么所有的NP问题都能在多项式时间内解决。

本文标签： PNPNPC概念总结

版权声明：本文标题：P、NP、NPC概念总结 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1687652764a125174.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。