こ，これは・・・
ECCCをチェックしてたら，こんな論文が･･･
R. Santhanam, "Circuit Lower Bound for Merlin-Arthur Classes"
メインの結果は非常にシンプルで，MA/1がP/polyに含まれない，つまり，1ビットアドバイス付きMAに属する言語で多項式サイズ論理回路で計算できない言語が存在する，という恐るべき結果です．これは相当NP≠Pの証明に近づいた気がします．この論文の著者のSanthanam氏は割りと最近シカゴ大のL. Fortnow氏*1とJ. Simon氏の下で学位をとってSimon Fraser大に就職した新進気鋭の研究者です．以前から１ビットアドバイス付きの確率的計算量クラスにおける階層定理に関する結果をここ数年出していたのは知っていましたが，今回の結果は以前の結果を大きく上回るインパクトを与えるかと思います．
５月２５日追記：メインの結果を勘違いしていました．Anonymousさんのコメント通り，任意の定数 k>0 に対して MA/1 に属して n^k サイズの論理関数で計算できない言語が存在する，ということでした．間違った事を書いてしまって申し訳ありません．つまり論文では MA/1 に属してかつ n^k サイズの論理関数では計算できない言語を定数 k ごとに構成しています．元々書いてたこと(MA/1とP/polyの分離)を証明するためには，MA/1に属するある一つの言語が存在して，任意のkに対してその言語を計算する n^k サイズの論理関数が存在しないことを言わなければいけません．もちろんSanthanam氏の結果はそれでも凄いものには変わりないとは思います．
