關於相信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。