P和NP问题（P versus NP problem）
P/NP问题是在理论信息学中计算复杂度理论领域里至今没有解决的问题，它也是克雷数学研究所七个千禧年大奖难题之一。学计算机的肯定会经常听到P和NP，但我相信很多人跟我一样对这个问题既熟悉又陌生，并不能真正地把他理解透彻，今天花点时间总结下吧。
什么是P问题？
能够在多项式时间内给出答案的问题被称为P问题，也就是说存在一个多项式时间复杂度内的算法解决该问题。这个很好理解，那为什么要是在多项式时间呢？因为只有在多项式时间内的复杂度才是计算机所能接受的，再大的复杂度（比如指数级，阶乘级别）即使有解也没有实际价值（计算量太大）。
什么是NP问题？
对有些问题而言，并不存在一个已知的多项式时间内的算法来解决问题，但是如果有人能够提供一个答案（不论对错），我们却能够很快地验证这个解是否正确，那么这些能够在多项式时间内验证一个解的问题被称为NP问题。通俗，不严谨的讲就是能在多项式时间内猜出解的问题。举个栗子：著名的子集合求和问题（subset sum problem），给定一个整数集合：{−2, −3, 15, 14, 7, −[……]