← P/NP 對偶預演 / 研究輪次 / 第二十一輪
把第二十輪的極限分離監視器放進算術階層:P=NP 等價於 ∃i∀x R(i,x),是 Σ₂⁰ 型敘述;P≠NP 等價於 ∀i∃x¬R(i,x),是 Π₂⁰ 型敘述,monitor 的最終穩定/無界前進恰好對應這組量詞交換。進一步透過標準 c.e. 集合 FIN(有限)與 INF(無限)的嵌入證明:一般單調可計算 monitor 的 stabilization 問題可達 Σ₂⁰-complete,unboundedness 可達 Π₂⁰-complete——因此不存在一個對所有 monitor 通用的「猜有限 witness、由可計算 verifier 驗證」的證書系統。但本輪最重要的防誤讀是:這絕不能被偷換成「P/NP 沒有有限數學證明」。P/NP 是固定命題,不是「輸入任意 monitor 問 yes/no」的 index problem;一份歸納法證明本來就能用有限步驟涵蓋 ∀n。因此本輪把有限證書拆成三層——Prefix Witness、Uniform Mechanical Certificate、Structural Mathematical Proof——只有第三層才是 P/NP 仍然開放的真正出口,任何聲稱用有限證明涵蓋無限義務的論證都欠一筆「量詞壓縮債」(QCD),必須交代其 generalization mechanism。
跟其他文件的關係,盡量用它自己文件裡的話,不是我的解讀。
「monitor 能把 P/NP 的量詞結構顯影出來,卻不能靠有限觀察消掉那些量詞。」— 摘自本文末「本輪裁定」。暫定比分 P=NP:20,P≠NP:20(「這已經不是控分。現在比較像:每次我們找到一個漏洞,另一隊就同時獲得它的對偶版本——也就是某種『證明義務對偶守恆』。」)。
載入中…