【机器学习】NP问题、P问题、NPC问题

NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。P类问题：所有可以在多项式时间内求解的判定问题构成P类问题。判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题。NP类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题。非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。NPC问题：

zkq_1986

11403人浏览 · 2018-01-08 14:30:51

zkq_1986  ·  2018-01-08 14:30:51 发布

 NP的英文全称是Non-deterministic Polynomial的问题，即多项式复杂程度的非确定性问题。

P类问题：所有可以在 多项式时间内求解的判定问题构成P类问题。 判定问题 ：判断是否有一种能够解决某一类问题的能行算法的研究课题。

NP类问题：所有的非确定性多项式时间可解的判定问题构成NP类问题。 非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。

NPC问题：NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)。

CSDN学习社区

CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！

加入社区

更多推荐

• · 用 OpenAI Assistants 做大模型应用开发
• · 1 小时解读鸿蒙 10 大热点问题
• · 1 小时解读鸿蒙 10 大热点问题

用 OpenAI Assistants 做大模型应用开发

CSDN学习社区

1 小时解读鸿蒙 10 大热点问题

CSDN学习社区

1 小时解读鸿蒙 10 大热点问题

CSDN学习社区

欢迎加入社区

取消 确定