P与NP问题

在了解P与NP问题之前，先看两个定义，一个是多项式时间复杂度，一个是指数型时间复杂度。

多项式时间复杂度的通项式子可以写成，a*n^k+b*n^(k-1)+……+z*n^0，n代表问题规模。

指数型时间复杂度的通项式子可以写成，k^n，n代表问题规模，k为大于1的常数，或者也可以写成 n! 这类型的式子。

P问题：

P问题指的是能用多项式时间计算出结果的问题，也称之为多项式问题。P是Polynomial，多项式的意思。

NP问题：

NP问题指的是能用多项式时间验证结果正确与否的问题，而不管计算出结果是用多项式时间还是指数型时间。

所有的P问题都是NP问题，因为既然能用多项式时间求得正确结果，那么验证结果正确与否肯定也是多项式时间，最不成就是重新计算一遍正确结果，肯定也是多项式时间。

但是是否所有的NP问题，也就是能用多项式时间验证的问题，都有一个计算正确结果的多项式时间复杂度的算法呢？这个还不知道，所以P=NP? 这个问题也悬而未决。

举个例子，TSP问题，100个城市，任意两个城市之间可以往返，从第一个城市出发，走遍所有城市，最后要回到第一个城市，城市与城市之间的通行费用不等。现在限制总的通行费用是cost，要求找到一条路径能够满足限制条件，而又能游遍所有城市并回到第一个城市。

如果我们要找到这样一条路径，需要遍历所有的可能情况，判断生成的每一条路径是否满足限制条件，一共有99！条这样的路径（假设第一个城市已经确定了下来，必须是从北京出发）。

但是如果我们要验证某一条游遍100个城市并回到第一个城市的路径，是否满足限制条件，只需要计算一下总的费用，便可以判断。

所以，TSP问题是NP问题，但目前还没有找到P的算法，也就是能用多项式时间复杂度计算出结果的算法。

感谢博客https://blog.csdn.net/bitcarmanlee/article/details/51935400的分享。

以下为笔者最近碰到的另一个NP问题，不感兴趣的可以不看啦~（闲聊性质）

笔者为什么最近会关注这个问题呢？因为在看sgbm的算法，博客https://www.cnblogs.com/hrlnw/p/4746170.html提到了sgbm的全局能量函数，说这个能量函数式子是个NP问题。

上述式子来源 Hirschmuller, H. Stereo Processing by Semiglobal Matching and Mutual Information, PAMI(30), No. 2, February 2008, pp. 328-341.

可能没有接触过双目视觉领域的同学不太懂这个式子是什么意思。

如果已知整张图片中所有像素点的视差，那么根据上述式子，我们自然就能得到能量E(D)是多少。但是想要求解得到全局最小的能量，我们需要遍历所有情况，这又是一个难以在P时间内求解的问题。

因此sgbm算法“近似分解该问题为多个一维问题，即线性问题。而且每个一维问题都可以用动态规划来解决。因为1个像素有8个相邻像素，因此一般分解为8个一维问题”。

感兴趣的同学可以看下上述博客的介绍，这里就不多讲了。