P、NP、NPC与NP-Hard问题（定义）
发布时间
阅读量：
阅读量
- P问题是被称为能在多项式时间内解决的任务。
- NP问题是可被快速验证的存在性判断任务，在此我们能确定所有的P类任务都属于其范畴然而关于P与NP的关系至今仍待证实无论是断言其相等性还是相反性都尚未得到证实。
- NPC（NP完全）问题是被认为是NP类别中最具挑战性的任务。要判定一个问题是否为NPC需遵循两个步骤首先是确认该问题是NP类的；其次是通过将一个已知的NPC难题转化为当前研究对象来完成这一过程由此可知首要的工作是设定第一个被广泛接受的NPC难题即电路可满足性定理。
- NP-hard问题是被认为至少与NP难度相当的一类任务
全部评论 (0)
还没有任何评论哟~