抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
複雑性理論における顕著な現在の課題の一つは,TC0のための下限,一定深さのクラス,多数ゲートを有する多項式サイズ回路を証明する試みである。Williams(2013)の結果に基づいて,そのような下限を証明するための魅力的なアプローチは,TC0のための非自明な脱ランダム化アルゴリズムを構築することである。本研究では,深さd>2のTC0回路の脱ランダム化に関する最初の正の結果を証明することにより,後者の目標に向けて最初の段階を取り上げた。著者らの最初の主な結果は,ワイヤの超線形数を有するTC0回路のための定量化された脱ランダム化アルゴリズムである。特に,深さdとn1+exp(-d)ワイヤでn入力ビット上でTC0回路Cを入力するアルゴリズムを構築し,ほぼ多項式時間で実行して,ほとんどの2n1-1/5d入力でのC拒絶と,Cが大部分の2n1-1/5d入力で受け入れる場合を識別した。事実,回路Cが線形閾値回路である場合でさえ,TC0回路(即ち,Cは線形閾値ゲートを持つ回路であり,それは大多数ゲートより強力である)よりも,このアルゴリズムは動作した。著者らの第2の主な結果は,著者らの定量化された脱ランダム化アルゴリズムの適度な改善でさえ,TC0のすべての標準脱ランダム化のための非自明なアルゴリズムをもたらして,その結果,NEXP⊆/TC0を暗示するであろうということであった。特に,深さdとn1+O(1/d)ワイヤ(n1+exp(-d)ワイヤより)のTC0回路を入力として得られる定量化された脱ランダム化アルゴリズムが存在するならば,ほとんどの2nexp(-d)で時間内に実行され,Cが大部分の2n1-1/5d入力で,そしてCが大部分の2n1-1/5d入力で受け入れられる場合と,Cが,TC0の標準脱ランダム化のために,2n1-Ω(1)の実行時間を有するアルゴリズムが存在する。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
