Finite Playground

To verify is human; to prove, divine.

NEXP do not have ACC0 circuits

Leave a comment

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

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

\mathsf{NTIME}(2^n)不能用\mathsf{ACC}^0circuits – 也就是 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}之後, 最重大的結果!!

Author: hcsoso

Ph.D. student in the Department of Computer Science, University of Illinois at Urbana-Champaign.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s