NP完全问题 npc _生活百科

npc(NP完全问题)【NP完全问题 npc】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问题。