关于相信 NP 不是 P 的一个奇怪思路

本文的 LaTeX 公式转义版可看这里：简书版。或者也可以转到本文的豆瓣版或 Medium 版。
本文中所用的 LaTeX 公式可用此插件来转义（点击“此插件”跳转到 GitHub 项目页）。

首先，如果 NP = P 的话，那就是说任意一个 NP 问题都可以转化为一个 P 问题。

这就是说，任何一个 NP 问题都可以在多项式时间内找到解答。

其次，TSP 问题是一个已知的 NP 问题。

因此，如果 NP = P，那么任何 TSP 问题都可以在多项式时间内找到解答。

尤其，如果一张地图可以本分割为不连通的多个部分，我们一样可以在多项式时间内证明这张图是被割裂的而非所有节点都能连起来的。

接着，如果 TSP 问题中连接两个节点的路径是非对称的（记为 nTSP 问题），它依然是一个 NP 问题。

然后，TSP 问题和 nTSP 问题都可以转化为一个有 n 个节点的离散空间中的最短闭合填充曲线问题。和它相关的，是给定起点 s 和终点 e 的离散空间中的最短填充曲线问题（记为 oTSP 问题）。

很显然，oTSP 问题如果是 P 的，所用计算步数为 $P_n$，那有 n 个节点的 nTSP 和 TSP 问题就可以在 $n(n−1)P_n$ 步内解决，因此如果 TSP 问题是 P 的，那 oTSP 问题也一定是 P 的；反之如果 oTSP 问题是 P 的，那 TSP 问题也一定是 P 的。

现在，我们假定一个 oTSP 问题所用的计算步数为 $P_n$，而寻找给定起点和终点之间的最短路径（记为 SSP 问题）需要计算 $Q_n$ 步，我们可以利用 $P_n$ 计算 $Q_n$ 的一个上限：

$$
Q_n \leq n! P_n
$$

这就是说，通过 oTSP 问题我们并不能得到关于 SSP 问题的任何线索，但翻过来，如果 SSP 问题不能转化为 P，那就是说 oTSP 问题无法转化为 P，从而 TSP 问题就无法转化为 P 问题。

同样，这里也要强调一下：如果 SSP 问题是 P 的，那这张地图上给定起点和终点之后到底能不能有一条路径连接两点，也可以在多项式时间内解决。

那 SSP 问题到底是不是 P 的呢？

在《AIT 中的信息与熵》和《AIT on Infinity and Quantum》中我们看到，图灵机的计算过程可以看作是在一个由图灵机构成的编码空间中、根据一组基础图灵机所描述的规则进行跳转的过程。

也就是说，如果我们将每个图灵机看作一个节点，那图灵机的运转过程就是在这个离散空间中不断跳转的过程。换言之，一个图灵机的运转过程可以视为一条连接代表输入的起点与代表输出的终点的路径。

因此，能接受输入并输出指定输出的图灵机最少需要运行多少步，就是这样一个由图灵机构成的离散空间中的 SSP 问题 — — 尤其，就如上面强调的，SSP 问题包含了判断输入与输出是否可以连通这点。

综上所述，我们可以得到这样的结论：

如果所有 SSP 问题都是可计算的，那停机判定就是可计算的 — — 起点是目标图灵机对应的点，终点是“可停机”与“不可停机”这两个状态对应的点 — — 在图灵机的实际中，输出状态和图灵机可以被编码到同一个空间中 — — 这就是说，我们求一下指定图灵机到“可停止”的最短路径长度，再求一下到“不可停机”的最短路径长度（这是求解两次 SSP 问题），我们就可以知道给定图灵机到底能不能停机了。

顺便说一下，这里也就是一开始强调两点间路径是非对称的原因：图灵机的世界中从输入到输出和从输出到输入，无论是执行步数还是图灵机长度，都是非对称的。

但是！这点已经被证明是不可计算的了！

也就是说，图灵机世界的停机问题作为一个 SSP 问题，是不可计算的。

也就是说，至少存在一类 SSP 问题，是不可计算的。

那也就是说，并非所有 SSP 问题都是可计算的。

而由于任何 SSP 问题和 oTSP 问题都存在计算步骤上的关联，前者所需的步骤既然是不可计算的，虽然后者比前者少了 n!，但也依然是不可计算的。

这就是说，至少存在一类 oTSP 问题，是不可计算的。

这就是说，至少存在一类 TSP 问题，是不可计算的。

也就是说，至少存在一类 NP 问题，其通用解法是不可计算的。

换言之，并非所有 NP 问题都是 P 问题。

即：NP≠P。

这个“论证”非常粗糙，只是一个大意，而且也很不严谨，所以未必就是真的。

这只是一共了一个有趣的考虑角度，来让人们更加相信，NP 真的不是 P。