計算量的識別不能
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/08 05:23 UTC 版)
任意の多項式時間機械 D {\displaystyle D} （識別機(distinguisher)という）と任意の多項式 P {\displaystyle P} に対し、ある k 0 {\displaystyle k_{0}} があって任意の k > k 0 {\displaystyle k>k_{0}} に対し | P r ( D ( X k ) = 1 ) − P r ( D ( Y k ) = 1 ) | < 1 / P ( k ) {\displaystyle |Pr(D(X_{k})=1)-Pr(D(Y_{k})=1)|<1/P(k)} となる時、 { X k } k ∈ N {\displaystyle \{X_{k}\}_{k\in N}} と { Y k } k ∈ N {\displaystyle \{Y_{k}\}_{k\in N}} は計算量的識別不能であるという。 定義からわかるように、計算量的識別不能は、計算能力を多項式時間に限定した場合に、見分けることができないことを意味する。 例：暗号理論の分野では、多くの計算量的識別不能を仮定している。例として以下のものがある． 平方剰余と平方非剰余 ディフィー・ヘルマン鍵共有の鍵と乱数
※この「計算量的識別不能」の解説は、「識別不能」の解説の一部です。
「計算量的識別不能」を含む「識別不能」の記事については、「識別不能」の概要を参照ください。
ウィキペディア小見出し辞書の「計算量的識別不能」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
このページでは「ウィキペディア小見出し辞書」から計算量的識別不能を検索した結果を表示しています。
Weblioに収録されているすべての辞書から計算量的識別不能を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から計算量的識別不能
を検索
Weblioに収録されているすべての辞書から計算量的識別不能を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から計算量的識別不能
を検索
- 計算量的識別不能のページへのリンク
