Algebrization

以前ちょっと小耳には挟んでいたのですが，NP≠Pの証明へのアプローチの難しさを示す結果が最近（といってもすでに二ヶ月ぐらい前ですが）AaronsonとWigdersonによって示されたようです．まだ論文自体は公表されていませんが，Aaronsonのブログのこの記事からMITでのセミナー資料が見れるようです．結果自体は Baker-Gill-Solovay の relativization の代数的一般化で，オラクル A だけでなくそのオラクル A の low-degree extension A~ というものも含めた relativization による証明テクニックに対する否定的な帰結を得ているようです．例えば今年の STOC で示された Santhanam のアプローチも（MA/1 が fixed poly-size circuit を持たない)もこのAlgebrizationの範疇に入ってしまうとのことが書かれています．いずれにせよ，正式な論文の公開が待たれます．