P与NP问题

什么是非确定性（Non-Deterministic）问题呢?

有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。

但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步步推算出来，下一个质数应该是多少呢?这样的公式是没有的。

再比如，大的合数分解质因数的问题，有没有一个公式，把合数代进去，就直接可以算出，它的因子各自是多少?也没有这样的公式。这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。

而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式（polynomial）时间内算出来，就叫做多项式非确定性问题。

而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。

完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。

但是这样算法的复杂程度，是指数关系，因此计算的时间随问题的复杂程度成指数的增长，很快便变得不可计算了。

什么是

P与NP问题的关系?

NP问题如果找到了多项式解法就是P问题了。NP问题是目前为止我们还未找到多项式解法的问题。我们也不能证明它一定存在或不存在多项式解法。

调查显示有的人持肯定态度，认为NP问题一定存在多项式解法，即P＝NP。

有的坚信NP问题不存在多项式解法。当然也有的人持不确定态度。

问题:P对NP问题是什么?

答:P对NP问题是Steve Cook于1971年首次提出。＂P/NP问题＂，这里的P指多项式时间（Polynomial），一个复杂问题如果能在多项式时间内解决，那么它便被称为P问题，这意味着计算机可以在有限时间内完成计算；NP指非确定性多项式时间（nondeterministic polynomial），一个复杂问题不能确定在多项式时间内解决，假如NP问题能找到算法使其在多项式时间内解决，也就是证得了P＝NP。

p对np问题

答:“P类”、“NP类”、“更复杂的类”，是确定型Turing机DTM中的不同复杂性分类。这些分类是由不同问题的性质决定的，还是我们目前没有找到好的DTM解决方法形成的?这就是“P对NP”问题上。它的基本意思是:（1）P＝NP:我们最终能够找到一些计算方法，使得NDTM能够快速解决的问题，在DTM上也能够快速解决。快速的意思是“使用不超过输入字符串的多项式时间”。（2）P≠NP:NP只能用NDTM快速解决，而不能用DTM快速解决。

如何

问题:如何解决NP问题?

答:一则证明NP等于P，从而从理论上找到NP问题的多项式时间算法；

二则证明NP不等于P，那么就可以归纳得知某些NP问题永远也不可能有多项式时间算法。

\

P！＝NP

问:P≠NP的答案是谁提出的?

答:美国惠普实验室的数学家维奈·迪奥拉里卡。

问题:论证P！＝NP。

答:如果P＝NP，那么每个答案很容易得到验证的问题也同样可以轻松求解。这将对计算机安全构成巨大威胁，目前加密系统的破解就相当于要将一个整数分解为几个因数的乘积，正是其求解过程的繁琐，才能杜绝黑客的入侵。

对于有些NP问题，包括因数分解，P≠NP的结果并没有明确表示它们是不能被快速解答的；但对于其子集NP完全问题，却注定了其无法很快得到解决。其中一个著名的例子就是旅行商问题（Travelling Salesman Problem），即寻找从一个城市到另一个城市的最短路线，答案非常容易验证，不过，如果P≠NP，就没有计算机程序可以迅速给出这个答案。

P＝NP

问题:假如我们证明了P＝NP，会怎样?

答案:假如证明了P＝NP，则NP问题都可以转化为P问题，也就是实际上不存在NP问题，那么现在的很多应用将失去了它的作用，如密码等。