当学习器把训练样本学得“太好”的时候，很可能已经把训练样本自身的一些特点当作了所有潜在样本都会具有的一一般性质，这样就会导致泛化（generalization）性能下降，这种现象在机器学习中成为过拟合（overfitting）。与过拟合相对的欠拟合（underfitting）。
有多种因素可能导致过拟合，其中最常见的情况是由于学习能力过于强大，以至于把训练样本中不太一般的特性都学到了，而欠拟合则通常是由于学习能力低下而造成的。欠拟合比较容易客服，例如在决策树学习中扩展分支，在神经网络学习中增加训练轮数等。而过拟合是无法彻底避免的，我们所能做的只是缓解，或者说减小其风险。可大致这样理解：机器学习面临的问题通常是NP甚至更难，而有效的学习算法必然是在多项式时间内运行完成，若可彻底避免过拟合，则通过经验误差最小化就能获得最优解，这就意味着我们构造性地证明了P=NP；因此，只要相信P<>NP，过拟合就不可避免。
以上来自机器学习摘抄。那么什么是P和NP呢？
1. P 问题 （Polynomial Time）- 多项式时间可解问题
能快速解决的问题（多项式时间内找到答案） 例子：排序数组、找最短路径
2. NP 问题（Nondeterministic Polynomial Time）- 非确定性多项式时间可验证问题
能快速验证答案的问题（多项式时间内验证给定答案是否正确）
注：P ⊆ NP（能解决的问题一定能验证答案）
例子：数独、旅行商路线验证
3. NPC 问题（NP-Complete）NP完全问题
NP 中最难的问题，且满足：
- 属于 NP（可快速验证答案）
- 所有 NP 问题都能转化为该问题（如果它被高效解决，则所有 NP 问题都能高效解决）
例子：SAT 布尔满足问题、背包问题
4. NP-Hard 问题（NP困难）
难度 ≥ NPC 的问题，但不一定属于 NP（可能无法快速验证答案）
关键：所有 NP 问题都能转化为它，但它本身可能比 NP 更难
例子：旅行商最优解、停机问题
- P = NP？（是否所有能验证的问题都能快速解决？）是计算机科学最大未解之谜。
- 实际意义：遇到 NPC/NP-Hard 问题，通常需用近似算法、启发式方法求近似解。
