本文主要是介绍P问题,NP问题,NPC问题,以及三者之间的关系,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、以下是从百度知道上转载来的关于P问题,NP问题,NPC问题的解释
1、P问题 P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数,则我们说这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解;P事实上很直观,我们通常在编程中求解的问题大多都是P类问题.比如说排序,找最短路径等.
2、NP问题
然而有些问题很难找到多项式时间的算法(或许根本不存在
这篇关于P问题,NP问题,NPC问题,以及三者之间的关系的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!