文献

J-GLOBAL ID：202002224338941812   整理番号：20A2013729

スパース集合の硬度と最小回路サイズ問題【JST・京大機械翻訳】

Hardness of Sparse Sets and Minimal Circuit Size Problem

著者 (1件)： Fu Bin (Department of Computer Science, University of Texas Rio Grande Valley, Edinburg, TX, USA)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12273  ページ： 484-495  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： ランダム化ストリーミングモデルにおける非決定論的時間複雑性クラスにおけるスパース集合の硬度の倍率を研究した。著者らの結果の1つは,[数式:原文を参照]更新時間と[数式:原文を参照]空間,次にf(n)-スパース集合が長さnのほとんどのf(n)ストリングを持つ言語である,[数式:原文を参照]で任意のランダム化ストリーミングアルゴリズムを持たない[数式:原文を参照]に[数式:原文を参照]スパース集合が存在することを示す。また,[数式:原文を参照]が多項式時間真実テーブル減少の下で[数式:原文を参照]困難であるならば,次に[数式:原文を参照]が,次に[数式:原文を参照]であることも示した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *言語 ,  硬度
準シソーラス用語： 複雑性 ,  多項式時間 ,  回路規模 ,  ストリーミングアルゴリズム ,  ランダム化 , 【Automatic Indexing@JST】

著者キーワード (4件)： MCSP ,  スパース集合 ,  拡大 ,  還元

分類 (1件)： 信号理論  (ND02020G)

タイトルに関連する用語 (3件)： 集合 ,  硬度 ,  回路サイズ