← P/NP 對偶預演 / 研究輪次 / 第七輪

第七輪 v1.0 2026-08-01

代數不變量爭奪戰:容易問題是否都有「可合成的解結構」?

Polymorphism 給出一個漂亮候選:不看公式怎麼寫,而看合法 tuple 能否被非平凡運算穩定合成——Horn 靠 AND 合成、dual-Horn 靠 OR、2-SAT 靠 majority、affine 靠 XOR/minority,更一般的有限域 CSP dichotomy 則以 Taylor/WNU 類運算為核心。這是目前整場遊戲中第一個真正跨越表面語法、且能無條件導出多項式演算法的結構性工具。但等號隊抓到本輪最重要的邏輯分界:CSP dichotomy 的 hard side 正式結論是 NP-complete,而 NP-complete 不等於不在 P,除非已經知道 P≠NP。若 P=NP,沒有 tractable polymorphism 的語言仍會有多項式演算法。提出 Algorithm-to-Algebra Bridge Problem:任意精確 P 演算法是否必然誘導某種可獨立定義的解空間合成結構?這座橋目前尚未建成。

第七輪雙假設預演 — 包內文件自陳的階段性狀態,原樣照登。

連接 · Connections

跟其他文件的關係,盡量用它自己文件裡的話,不是我的解讀。

「Polymorphism 能刻畫已知 structural tractability,但尚不能證明它是『任何可能 P 演算法』的必要條件。」— 摘自本文第六節「等號隊反殺」。核心橋問題:「A∈P ⟹ 某種可獨立刻畫的 nontrivial induced structure?」— 摘自本文第十八節「本輪正式戰果」。暫定比分 P=NP:6,P≠NP:6。

載入中…