表示逃逸錦標賽:哪些困難被哪種數學武器打穿?

不再先猜一個終極不變量,而是讓五個經典困難族(Tseitin/XOR、Pigeonhole、Clique、一般 SAT、TSP/CUT/Stable Set 多面體)逐一對上六種表示武器(resolution、代數化、單調電路、樹寬分解、知識編譯、LP 擴展表示),每格只給「逃逸」「下界」或「未知」三種裁定。矩陣立刻顯示:沒有任何一列在所有欄位同時形成一般下界,也沒有任何一種武器能普遍逃逸——Clique 在單調電路的強下界不能外推一般電路(negation 被禁止就是關鍵原語缺失),TSP/CUT 多面體的 LP 擴展複雜度下界只限制線性表示。提出表示逃逸剖面 REP,把研究對象從「困難度」改寫成「困難度相對於哪種表示」的二元關係。