趣題：怎樣向別人證明兩個圖不同構？
若干個頂點（vertex）以及某些頂點對之間的邊（edge）就構成了一個圖（graph）。如果圖 G 和圖 H 的頂點數相同，并且它們的頂點之間存在著某種對應關系，使得圖 G 中的兩個頂點之間有邊，當且僅當圖 H 中的兩個對應頂點之間有邊，我們就說圖 G 和圖 H 是同構的（isomorphism）。直觀地說，兩個圖是同構的，意思就是它們本質上是同一個圖，雖然具體的畫法可能不一樣。下面的兩個圖就是同構的。其中一種頂點對應關系是： 1 – a, 2 – c, 3 – d, 4 – b, 5 – e, 6 – g, 7 – h, 8 – f 。
目前，人們還沒有找到任何高效的算法，能迅速判斷出兩個圖是否同構。在普通計算機上，判斷兩個圖是否同構，這需要花費大量的時間。因此，人們經常以圖的同構為例，來解釋復雜度理論和現代密碼學中的諸多概念。
假設你家里的計算機十分強大，能很快判斷出兩個圖是否同構，還能在兩個圖確實同構的情況下，給出一種頂點對應關系。但你的同桌家里的計算機卻非常弱，沒法做什么大型運算。課堂上，老師向全班展示了兩個很復雜的圖，不妨把它們叫作圖 G 和圖 H 。老師布置了一個特別的選做題：判斷出這兩個圖是否同構。每個同學都可以提交答案，答案里只需要寫“是”或者“不是”即可。按時提交答案并答對者，期末考試會獲得 5 分加分；按時提交答案但答錯了的，期末考試成績將會倒扣 30 分；不參與此活動的同學，期末考試既不加分也不扣分。顯然，每個同學都不敢隨意提交答案，除非百分之百地能保證自己獲得的答案是正確的。回到家后，借助家里的超級計算機，你很快判斷出了這兩個圖是同構的。你給你的同桌發送了信息：“我已經算出來了，這兩個圖是同構的。”但是，你的同桌卻回復說：“你不會是騙我的吧？”你打算怎樣說服他，這兩個圖確實是同構的呢？
你只需要把兩個圖的頂點對應關系發送給他即可。他家里的計算機非常弱，沒法找出滿足要求的頂點對應關系。但若有了一個頂點對應關系，驗證其確實滿足要求，這是非常容易的，幾乎不需要什么計算量——只需要枚舉圖 G 里的頂點對，看看它們之間有邊是否當且僅當圖 H 中的對應頂點之間有邊即可。完成驗證之后，他就知道了，這兩個圖確實是同構的。
總結起來，剛才我們面對的是這樣的困境：
- 你擁有無限的計算能力。
- 對方的計算能力非常有限。
- 你想要向對方證明，圖 G 和圖 H 確實是同構的。
判斷兩個圖是否同構可能很難，但若給出一段證據后，很容易驗證兩個圖確實同構，上述困境也就得以解決了。這就是復雜度理論中 NP 問題的大致意思。
但是，如果把兩個圖同構的證據直接交給你的同桌，你的同桌或許又會用同樣的辦法去幫助別人，最后搞得班上所有人都獲得了加分，這就沒意思了。有沒有辦法說服你的同桌，這兩個圖確實是同構的，但卻又讓他無法拿到這兩個圖同構的證據呢？也就是說，現在我們面對的是這樣的困境：
- 你擁有無限的計算能力。
- 對方的計算能力非常有限。
- 你想要向對方證明，圖 G 和圖 H 確實是同構的。
- 你不想泄露這兩個圖的頂點之間的對應關系。
這看上去似乎是不可能實現的——不把頂點之間的對應關系告訴對方，怎樣說服對方兩個圖確實是同構的呢？然而，這竟然是能做到的。整個過程分為很多輪進行。在每一輪里，你隨機生成一個與圖 G 同構的圖 G′ 。如果圖 G 和圖 H 真的同構，那顯然圖 G′ 也與圖 H 同構。然后，你把圖 G′ 發送給對方。對方可以隨機提出下面兩個要求之一：提供 G′ 與 G 同構的證據，或者提供 G′ 與 H 同構的證據。不管對方提出的是哪個要求，你都可以放心大膽地把證據發給對方，這不會泄露圖 G 和圖 H 之間的對應關系。另外，如果圖 G 和圖 H 不是同構的，那么這兩個要求你不可能都做得到；面對對方的抽查，總能如約作答的概率是很低很低的。很多輪過去后，對方便慢慢確信，圖 G 和圖 H 真的是同構的了。在現代密碼學中，讓對方相信命題的正確性，但又不泄露任何其他的信息，這就叫作“零知識證明”（zero-knowledge proof）。
現在，讓我們再來看一種情境。去掉上述第四點要求，但把第三點要求改一下：
- 你擁有無限的計算能力。
- 對方的計算能力非常有限。
- 你想要向對方證明，圖 G 和圖 H 確實是不同構的。 </ul>
你打算怎么辦？注意，你的辦法應該普遍適用于一切情況。在某些特定的情況下，你當然可以告訴對方，“這兩個圖顯然不同構，因為它們的邊數就不一樣多”，但這不適用于兩個圖的邊數一樣多的情況。
很簡單。每次讓對方隨機生成一個與圖 G 同構的圖或者與圖 H 同構的圖，并把它發送給你。每次你都可以準確地告訴對方，剛才發來的圖是從圖 G 變過來的，還是從圖 H 變過來的。多試幾次，對方便能確信，這兩個圖確實是不一樣的。
上述所有例子都屬于“交互式證明”（interactive proof）。第一個例子是確定性的交互式證明（deterministic interactive proof）。它也是最簡單的一類交互式證明。第二個例子則是帶有附加條件的交互式證明。也就是說，零知識證明是一種特殊的交互式證明。第三個例子則表明，對于有些問題來說，交互式證明的存在性并不是顯然的（即使沒有任何附加條件）。如果利用確定性的交互式證明，你能向別人說明問題的答案是肯定的，我們就說這個問題屬于 dIP 集合。很容易證明， dIP = NP 。如果利用交互式證明（包括非確定性的交互式證明），你能向別人說明問題的答案是肯定的，我們就說這個問題屬于 IP 集合。交互式證明理論的一個最主要的結論就是 IP = PSPACE ，其中 PSPACE 表示所有能用多項式的空間解決的問題。
第一個例子和第二個例子都是我早已聽說過的例子。第三個例子以及與此相關的交互式證明理論則是我最近在 Introduction to the Theory of Computation 一書中看到的。它們應該都是復雜度理論中非常經典的例子。
來自: www.matrix67.com