NP&P精确逻辑运算之极限

有的时候我们会忘记行李箱的密码。这时候只能从000试到999。平均用时10分钟左右。而输入一个密码看看对不对只要1秒。这种现象，告诉我们，验证一个答案往往比找到答案方便许多。

NP（nondeterministic polynomial)问题集合是所有能在多项式时间内验证答案是否正确的集合。P（polynomial）问题集合是所有能在多项式时间内找到答案的集合。所谓多项式时间，指的是最坏情况下所用加减逻辑运算次数是像n^3+n^2+2这样的多项式，n是问题的规模。比如问题：暴力破解n位数密码。所用次数最坏10^n次，是指数式，比多项式增长快得多，所以不是P问题。但是验证一个密码是否正确，一次就行（1是多项式），所以是NP问题。

注：NP是一个问题集合。属于NP的问题简称为“NP问题”。

世界未解之谜：NP是否等于P？

注：机械密码锁的问题其实是一个P问题。因为我们在解决问题的时候是以对系统完全了解为前提的。如果我有一台X光透视仪，又具备锁匠全部的知识，我可能是可以一眼看出密码是多少的（也许锁的设计是有迹可循的，比如我看到有小凹槽的地方就确定是密码点，注意：通过对锁知识的加深，我改进了我的算法（从暴力尝试到找小凹槽））。我需要花很长时间破解机械密码锁的密码只是因为我没有对锁内部结构的了解，而研究NP与P的时候是假定对问题系统有充分的了解的。

抛开人类未解之谜不谈。对NP和P的研究告诉我们：不仅人类是有极限的，计算机逻辑运算的算法也是有极限的，而且这个极限，还挺低的。

计算机的核心是能够进行逻辑运算(与、或、非）的电路。假设对于这样一个电路，它有八个输入端口，有一个输出端口。现在目标是：让输出为1。比如现在输入高低电压（10101110），发现输出端口给出了高电压（1），整个过程极度方便（计算量为1），故是NP。那么想要让输出为1，需要怎样的输入呢？

最简单的：暴力尝试。最坏需要2^8次。如果有n个输入端口，就需要2^n次，指数量级。

为了更快一些，我们决定观察一下电路板。和机械锁上有小凹槽不同，电路板只是一些逻辑电路叠加在一起。是否可以设计一个程序，把电路板的信息输入进去，它就可以在多项式时间内解出怎么让输出为1呢？（目前还没找到符合这样的程序）

注：电路板的复杂程度也计算在问题的规模中。比如电路板会进行m次逻辑运算，输入引脚有n个。那要是P的话解决问题所花时间就要同时是n和m的多项式。

注：在研究NP和P的问题时，研究的是普遍情况。比如给出一个进行m次逻辑运算有n个输入引脚的电路板。假设所有逻辑运算均为“非”运算，那么你也许可以通过观察电路迅速得出结果。但要声称这是一个P问题，你必须对任意一种进行m次逻辑运算有n个输入引脚的电路板都能在多项式时间内找到答案。

这个逻辑电路板问题就是NP问题的鼻祖：Circuit Satisfiability Problem。让我们把它作为NP-C(complete)的第一个成员。

暂时引入记号