可解閉包穩定性與多項式鏈爆炸:每一步都容易,整條路就一定容易嗎?

前十二輪一直在找「這一步是否 tractable」,本輪證明這個問題本身不夠。若表示大小滿足 s_(t+1)=s_t^d(d≥2),每一步相對當前表示大小都是多項式變換,但從 s_0=n 出發 m 步後 s_m=n^(d^m)——只要步數 m 隨輸入增長,整體便迅速超出任何固定多項式界,且不需要涉及 SAT,純粹是演算法設計的組合陷阱。正式區分 Stepwise Polynomiality(相對當前表示的局部多項式)與 Pathwise Polynomiality(相對原始輸入的全程多項式),提出可解閉包穩定性(TCS)要求步數、峰值表示、累積成本、答案還原成本都對原始輸入統一多項式有界。等號隊被迫升級成攤銷可解證書(ATC),不等號隊則提出路徑不穩定猜想(PCIC)。