抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
最小回路サイズ問題(MCSP[s(m)])において,長さn=2^mの与えられた信頼テーブルを計算するサイズs(m)の回路があるかどうかを検討した。最近,MCSP[s(m)]に対して[OliviraとSanthanam,FOCS2018]による硬度拡大と呼ばれる驚くべき現象が発見され,計算時間有界Kolmogorov複雑性の関連問題MKtPが発見された。[OliviraとSanthanam,FOCS2018],[Olivira,Pich,Santhanam,CCC2019],[McKay,Murray,Williams,STOC2019]では,NPのような小さい(n^{1+eps})下限はNPのような低い限界を意味し,NPはNC ^1ではなく,EXPはP/ポリではないことを示した。著者らは,問題を考察した。それは,MCSPとMKtPについて特別である。なぜそれらがこの顕著な現象を容認するか?一つの簡単な特性は,以前の研究で考慮されたMCSP(およびMKtP)のすべての変種がスパース言語であるということである。例えば,MCSP[s(m)]は長さn=2^mの2つの^{O(s(m))}を持ち,そのためMCSP[2^o(m)]は2つの^{n ^o(1)}-スパースである。すべての等しいNP言語に対して,硬度拡大現象が存在することを示した。形式的には,2つの^{n ^o(1)}-スパースであるNPにおいて,eps>0と言語Lがあり,LはCircuit[n ^{1+eps}]ではない。次に,NPはすべてのkに対してn個のサイズ回路を持たない。De Morgan式,B_2式,分岐プログラム,AC ^0[6]およびTC ^0回路に対する類似の定理を証明し,さらに,指数におけるeps因子によるNP下限における最先端の状態の改善は,すべての固定多項式に対するNP下限を意味する。事実,著者らの証明において,L:1に対する(すなわち,1+eps)回路サイズ下限を証明することは必要でない。1つは,n個の^epsアドバイスビットを持つn^{1+eps}-時間n-空間決定論的アルゴリズムに対する下限を証明しなければならない。このような下限は非スパース問題に対してよく知られている。著者らの技術に基づいて,search-MCSPとsearch-MKtPのための興味ある新しい硬さ倍率を示した。すなわち,Parity-P(またはPP,PSPACE,EXP)のような結果は,P/ポリ(またはNC ^1,AC ^0[6]または多項式サイズの分岐プログラム)に含まれない。例えば,search-MCSP[2^{βm}]が,すべての定数β>0に対して,サイズn^{3+eps}のDe Morgan公式を持たないような場合には,それから,○+-P NC ^1がある。Copyright 2020 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
