nexp | Finite Playground

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

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

$\mathsf{NTIME}(2^n)$ 不能用 $\mathsf{ACC}^0$ circuits – 也就是 constant-depth, poly-size circuits with AND, OR, NOT, and Mod_m gates for any m 解掉.

這個結果有多大呢? 說大也不大, 因為人們相信就連 $\mathsf{NP}$ – 比 $\mathsf{NTIME}(2^n)$ 小太多的問題集合都不可能被 poly-size circuits – 比 $\mathsf{ACC}^0$ 大太多的 circuits 解掉. 換句話說, 離 $\mathsf{P} \neq \mathsf{NP}$ 還有很遠.

可是那又如何? 這可是一個新的 lower bound 結果! 上過 complexity 就知道 lower bounds 有多麼難得到… 在 Ryan Williams 之前, 我們連 $\mathsf{NTIME}(2^n)$ 能不能用 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 $\mathsf{L}$ 之後, 最重大的結果!!

Finite Playground

To verify is human; to prove, divine.

Tag Archives: nexp

NEXP do not have ACC0 circuits