文献

J-GLOBAL ID：202202273205652918   整理番号：22A0773802

1つのNPオラクル問合せによる増幅【JST・京大機械翻訳】

Amplification with One NP Oracle Query

著者 (1件)： Watson Thomas (Department of Computer Science, University of Memphis, Memphis, USA)
資料名： Computational Complexity  (Computational Complexity)
巻： 31  号： 1  ページ： 3  発行年： 2022年 
JST資料番号： W2250A  ISSN： 1016-3328  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 成功確率の増幅が1つのNPオラクルクエリへのアクセスを持つランダム化アルゴリズムに対して,2側面,片側,およびゼロサイドエラーの設定において可能となる範囲の完全な描像を提供する。この描像を,q-queryアルゴリズムで1つの質問アルゴリズムを増幅するために一般化し,著者らの介在物は,再分割技術に対してタイトであることを示した。Copyright The Author(s), under exclusive licence to Springer Nature Switzerland AG 2022 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *質問 ,  *データベース管理システム ,  介在物
準シソーラス用語： *オラクル ,  成功率 ,  ランダム化 , 【Automatic Indexing@JST】

著者キーワード (3件)： 増幅 ,  NP ,  オラクル

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (4件)： Np ,  オラクル ,  問合せ ,  増幅