P问题、NP问题、NPC问题 区分与介绍

时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。

复杂度被分为两种级别：
一种是O(1),O(log(n)),O(n^a) (a为常数)等，我们把它叫做多项式级的复杂度，因为它的规模n出现在底数的位置； 另一种是O(a^n)和O(n!)型复杂度，它是非多项式级的，其复杂度计算机往往不能承受。
当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。


P类问题的概念：
如果一个问题可以找到一个能在多项式的时间里解决它的算法，那么这个问题就属于P问题。P是英文单词多项 式的第一个字母。
哪些问题是P类问题呢？通常NOI和NOIP不会出不属于P类问题的题目。常见到的一些信息奥赛的题目都是P问题。道理很简单，一个 用穷举换来的非多项式级时间的超时程序不会涵盖任何有价值的算法。

NP问题的概念:
NP问题是指可以在多项式的时间里验证一个解的问题。
NP问题的另一个定义是，可以在多项式的时间里猜出一个解的问题。
NP问题不是非P类问题!

之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。我们不会指望一个连多项式地验证一个解都不行的问题存在一个解决它的多项式级的算法。相信读者很快明白，信息学中的号称最困难的问题——“NP问题”，实际上是在探讨NP问题与P类问题的关系。

关键是，人们想知道，是否所有的NP问题都是P类问题。我们可以再用集合的观点来说明。如果把所有P类问题归为一个集合P 中，把所有NP问题划进另一个集合NP中，那么，显然有P属于NP。现在，所有对NP问题的研究都集中在一个问题上，即究竟是否有P=NP？通常所谓的 “NP问题”，其实就一句话：证明或推翻P=NP。

目前为止这个问题还“啃不动”。但是，一个总的趋势、一个大方向是有的。人们普遍认为，P=NP不成立，也就是说，多数人相信，应该 至少存在一个不可能有多项式级复杂度的算法的NP问题。人们如此坚信P≠NP是有原因的，就是在研究NP问题的过程中找出了一类非常特殊的NP问题 叫做NP-完全问题，也即所谓的NPC问题。C是英文单词“完全”的第一个字母。正是NPC问题的存在，使人们相信P≠NP。下文将花大量篇幅介绍NPC 问题，你从中可以体会到NPC问题使P=NP变得多么不可思议。

NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题：首先，它得是一个NP问题；然后，所有的NP问题都可以约化到它。

约化(Reducibility，有的资料上叫“归约”)：
简单地说，一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可以“变成”问题B。
  “问题A可约化为问题B”有一个重要的直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。这很容易理解。既然问题A能 用问题B来解决，倘若B的时间复杂度比A的时间复杂度还低了，那A的算法就可以改进为B的算法，两者的时间复杂度还是相同。
   很显然，约化具有一项重要的性质：约化具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。


   如果不断地约化上去，不断找到能“通吃”若干小NP问题的一个稍复杂的大NP问题，那么最后是否有可能找到一个时间复杂度 最高，并且能“通吃”所有的NP问题的这样一个超级NP问题？答案居然是肯定的。也就是说，存在这样一个NP问题，所有的NP问题都可以约化成它。换句话 说，只要解决了这个问题，那么所有的NP问题都解决了。这种问题的存在难以置信，并且更加不可思议的是，这种问题不只一个，它有很多个，它是一类问题。这 一类问题就是传说中的NPC问题，也就是NP-完全问题。NPC问题的出现使整个NP问题的研究得到了飞跃式的发展。我们有理由相信，NPC问题是最复杂 的问题。


不要以为NPC问题是一纸空谈。NPC问题是存在的。确实有这么一个非常具体的问题属于NPC问题。下文即将介绍它。
    下文即将介绍逻辑电路问题。这是第一个NPC问题。其它的NPC问题都是由这个问题约化而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。
    逻辑电路问题是指的这样一个问题：给定一个逻辑电路，问是否存在一种输入使输出为True。
    什么叫做逻辑电路呢？一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻的线组成。看下面一例，不需要解释你马上就明白了。
  ┌───┐
  │ 输入1├─→┐    ┌──┐
  └───┘    └─→┤    │
                     │ OR ├→─┐
  ┌───┐    ┌─→┤    │    │    ┌──┐
  │ 输入2├─→┤    └──┘    └─→┤    │
  └───┘    │               ┌─→┤AND ├──→输出
               └────────┘ ┌→┤    │
  ┌───┐    ┌──┐            │  └──┘
  │ 输入3├─→┤ NOT├─→────-┘
  └───┘    └──┘
    这是个较简单的逻辑电路，当输入1、输入2、输入3分别为True、True、False或False、True、False时，输出为True。
    有输出无论如何都不可能为True的逻辑电路吗？有。下面就是一个简单的例子。
  ┌───┐
  │输入1 ├→─┐    ┌──┐
  └───┘    └─→┤    │
                     │AND ├─→┐
               ┌─→┤    │    │
               │    └──┘    │  ┌──┐
               │               └→┤    │
  ┌───┐    │                   │AND ├─→输出
  │输入2 ├→─┤  ┌──┐      ┌→┤    │
  └───┘    └→┤NOT ├→──┘  └──┘
                   └──┘
    上面这个逻辑电路中，无论输入是什么，输出都是False。我们就说，这个逻辑电路不存在使输出为True的一组输入。
    回到上文，给定一个逻辑电路，问是否存在一种输入使输出为True，这即逻辑电路问题。
    逻辑电路问题属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以直接证明所有的NP问题都可以约化到它（不要以为NP问题有无穷多个将给证 明造成不可逾越的困难）。证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。
    有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题约化到它就行了。后来，Hamilton 回路成了NPC问题，TSP问题也成了NPC问题。现在被证明是NPC问题的有很多，任何一个找到了多项式算法的话所有的NP问题都可以完美解决了。因此 说，正是因为NPC问题的存在，P=NP变得难以置信。P=NP问题还有许多有趣的东西，有待大家自己进一步的挖掘。攀登这个信息学的巅峰是我们这一代的 终极目标。现在我们需要做的，至少是不要把概念弄混淆了。

学习了一下 P问题、NP问题、NPC问题的概念，摘抄了过来，原文参考：
，原文更精彩。