读书笔记摘抄新闻资讯npc(NP完全问题)
npc，指NP完全问题（Non-deterministic Polynomial complete problem）。简单的说，如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那幺这个NP问题就称为NPC问题。
基本介绍
- 中文名：npc
- 外文名：Non-deterministic Polynomial complete problem
- 所属学科：理论信息学
- 作用：计算複杂度理论
在理论信息学中的计算複杂度理论领域里NPC指NP完全问题（Non-deterministic Polynomial complete problem）。
简单的说，如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那幺这个NP问题就称为NPC问题。
换言之，如果这个问题解决了，那幺所有NP问题也都能解决了。第一个被证明是NPC的问题是3SAT问题。
目前为止我们还不能证明NPC问题有多项式算法（即NP等于P），也不能证明NPC问题没有多项式算法（即NP不等于P）。
关于更详细的介绍请参看NP问题。