NEXP do not have ACC0 circuits

幾乎所有重要的 Complexity Theorists 的部落格上都有這條新聞…

簡單來說, Ryan Williams 在 11/8 證明了關於 circuit lower bound 的新結果:

不能用circuits – 也就是 constant-depth, poly-size circuits with AND, OR, NOT, and Mod_m gates for any m 解掉.

這個結果有多大呢? 說大也不大, 因為人們相信就連 – 比 小太多的問題集合都不可能被 poly-size circuits – 比大太多的 circuits 解掉. 換句話說, 離還有很遠.

可是那又如何? 這可是一個新的 lower bound 結果! 上過 complexity 就知道 lower bounds 有多麼難得到… 在 Ryan Williams 之前, 我們連 能不能用 constant-depth, poly-size circuits with Mod_6 gates (沒有 AND 跟 OR!!) 解掉都不知道!!

另外, 它使用的技巧也很符合之前 Ketan Mulmuley 提出的 GCT 計畫中, 用 “證明上界” 來 “證明下界” 的概念. 在這篇突破性的論文中有使用到 Ryan 自己在 STOC ’10 中的論文 “Improving exhaustive search implies superpolynomial lower bounds“. 這使得這個方向的研究又再一次活過來了, 尤其是當有二三十年 circuit lower bound 沒有新的眾大突破結果下, 大家慢慢對 circuits 失去信心時…

有興趣的除了看上面的網誌介紹之外, 趕緊看看 Ryan Williams 的論文, 這應該是繼 Reingold 的 undirected reachability in 之後, 最重大的結果!!