Question

npc是什么意思?

Answer 1

npc指NP完全问题。

简单的说，如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NPC问题。还不能证明NPC问题有多项式算法（即NP等于P），也不能证明NPC问题没有多项式算法（即NP不等于P）。

NP完全问题延伸：

NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。而如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题，那么这个NP问题就称为NP完全问题（Non-deterministic Polynomial complete problem）。 

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