抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ある複雑性理論設定において,ほとんどどこでも,すなわち,有限に多くの入力長に対して,ほとんどどこでも保持する複雑性分離を証明することは,非常に難しい。例えば,古典的未解決問題は,NEXPがi.o.-NPに含まれるかどうかである。すなわち,非決定論的指数時間計算がNPアルゴリズムによって無限に多くの入力長さでシミュレートできるかどうかは,オープンである。この困難は,回路下限[Williams,J.ACM2014]に対するWilliamsのアルゴリズム法にも適用されている。[Murray and Williams,STOC 2018]は,非決定論的準多項式時間がACC>0に含まれないが,一方,NPオラクルを有するE≡NP(2^O(n)時間)がi.o.-ACC>0に含まれないことを示す未解決の問題を残した。本論文では,アルゴリズム手法によって証明される多くの無限大の回路下限が,ほとんどどこに低い限界を確立するのに適合できるかを示した。最初に,著者らは,すべての十分に大きな入力長nに対して,fは長さn(すべての小さなeに対して)の入力に関してexp(n→e)サイズACC>0回路によって近似される(1/2+exp(-n∧e)),すなわち,[ChenおよびRen,STOC2020]および[Viola,ECCC2020]における下限を改善する,というようなE^NPにおいて関数fがあることを示した。第2に,[AlmanとChen,FOCS 2019]と[Bhangale et al.2020]のように,無限にしばしば多くの入力に対して,P→NPの剛体行列を構築した。第3に,著者らは,E^NPがすべての大きなnに対して少なくともcn/(log|≦2n)で一定の誤差確率度を持ち,[Viola,ECCC2020]によって無限に分離する分離を改善することを示した。ほとんどどこでも最悪ケースの下限を証明するための著者らの鍵は,[FortnowとSanhanam,CCC2016]によって証明されたNTIME階層定理の新しい「構成」証明であり,ここでは,「弱い」非決定論的アルゴリズムに対して,ハード言語に対する”bad”入力を構築できる”refutterアルゴリズム”が存在する。このrefutterアルゴリズムを用いて,ほとんどどこでも硬い関数を構築した。平均ケースに下限を拡張するために,近似線形和に基づく新しいXOR Lemmaを証明し,それを[ChenとWilliams,CCC 2019]と[ChenとRen,STOC2020]で開発した近接アイデアのPCPと結合させた。著者らの新しいXOR Lemmaの副産物として,著者らは,[ChenとRen,STOC2020]における未解決の質問を解決する,シード長ポリログ(n)を有するポリサイズのACC>0回路のための非決定論的擬似ランダム発生器を得た。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
