ECCCをチェックしてたら,こんな論文が・・・R. Santhanam, "Circuit Lower Bound for Merlin-Arthur Classes"メインの結果は非常にシンプルで,MA/1がP/polyに含まれない,つまり,1ビットアドバイス付きMAに属する言語で多項式サイズ論理回路で計算できない言…
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。