我们在研究一个问题之前，首先得搞明白这个问题能不能解，如果能解，这个问题究竟有多难。而我们衡量一个问题有多难，则主要看该问题是否能够在多项式时间内可解。P问题、NP问题等名词的提出就是为了区分一个问题到底有多难。
P问题、NP问题等概念都是针对判定性问题的。判定性问题，即只需要回答YES或者NO的问题。
在本文中，我们只讨论判定性问题。
P代表了Polynomial，即多项式。
P问题：多项式时间可解的判定问题
P类问题：所有多项式时间可解的判定问题组成的问题类
NP的英文全称是Non-deterministic Polynomial，直译为多项式复杂程度的非确定性问题，也就是在多项式时间内不确定是否有解的问题。
NP问题：多项式时间可验证的判定问题
NP类问题：所有多项式时间可验证的判定问题组成的问题类
需要注意的是，不能简单地把问题分为P问题和NP问题。首先，这两类问题只是用来研究判定性问题的。其次，还有很多无法在多项式时间内验证的问题，这一类问题既不属于P问题，也不属于NP问题，这一类问题由于太难，所以研究价值比较低。最后，P问题与NP问题并不是对立的，显而易见，所有P问题都是NP问题，因为P问题既然多项式时间内可解，那么一定多项式时间内可验证。所以，P ∈ \in ∈NP。
NPC问题，即NP完全问题，是学者在研究“P=NP？”问题时提出的一个概念。
NPC问题：NP问题中最难的问题，所有NP问题都可以归约到该问题。
NPC类问题：NP问题中最难的问题不止一个，而是有很多这样的问题，且这些问题之间相互等价，这一类问题统称为NPC问题。
如果能找到一个NPC问题的多项式时间解法，那么就可以证明P=NP；如果可以证明一个NPC问题没有多项式时间解法，那么就可以证明P ≠ \neq =NP。NPC问题在计算复杂性理论中的地位可见一斑。
SAT问题，即布尔可满足性问题。
SAT问题：输入为一个布尔表达式，询问是否存在一组布尔变量，使得该布尔表达式的值为TRUE。
举例：给定布尔表达式 ( x 1 ∨ x 2 ) ∧ ( ? x 2 ∨ x 3 ) ∧ ( ? x 1 ∨ ? x 3 ) (x_1 ∨ x_2) ∧ (?x_2 ∨ x_3) ∧ (?x_1 ∨ ?x_3) (x1?∨x2?)∧(?x2?∨x3?)∧(?x1?∨?x3?)，询问是存在一组 ( x 1 , x 2 , x 3 ) (x_1,x_2,x_3) (x1?,x2?,x3?)，使得该表达式的值为TRUE。
输出：YES
分析：在布尔表达式中，∨表示并（or），∧表示交（and），?表示非（not）。其实存在很多组变量取法，可以使得该表达式为TRUE，比如（1，0，0），（0，1，1）等。
这个问题也是第一个被证明出来的NPC问题。
划分问题又叫PAR问题（Partition Problem）。
划分问题：输入一些数，询问是否能将这些数划分为加和相等的两部分。
举例：给出如下数：1，11，3，4，5，请问能否将这些数划分为加和相等的两部分。
输出：YES
分析：1+11=3+4+5，可以将这些数划分为{1,11}和{3,4,5}。
“P=NP？”问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它被“克雷数学研究所”在千禧年大奖难题中收录。
此处，P代表了P类问题，NP代表了NP类问题。该千禧难题的含义为，是否所有多项式时间可验证的判定问题都能在多项式时间内可解。目前该问题还没有被解决。
本文简单介绍了P问题、NP问题、NPC问题。这些都是计算复杂性理论中的专有名词。希望能够对大家有帮助。