乱択通信複雑性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/08 03:46 UTC 版)
上述の定義では、通信は決定論的に行われると見なしている。両者が乱数発生器にアクセスする場合、 f {\displaystyle f} の値をなるべく少ない通信量で決定することはできるだろうか？ ヤオは彼の論文[1979]で乱択通信複雑性を定義することでこの問題の回答を与えた。 関数 f {\displaystyle f} のための乱択プロトコル R {\displaystyle R} は、以下の両側誤りを持つ。 Pr [ R ( x , y ) = 0 ] ≥ 1 2 , if f ( x , y ) = 0 {\displaystyle \Pr[R(x,y)=0]\geq {\frac {1}{2}},{\textrm {if}}\,f(x,y)=0} Pr [ R ( x , y ) = 1 ] ≥ 1 2 , if f ( x , y ) = 1 {\displaystyle \Pr[R(x,y)=1]\geq {\frac {1}{2}},{\textrm {if}}\,f(x,y)=1} 乱択プロトコルは通常の入力以外に追加のランダム列を使用する決定論的プロトコルである。これには2種類のモデルがある。両者が事前に同じランダム列を共有している「公開ランダム列」と、一方が生成して他方に通信によって伝える必要のある「秘密ランダム列」である。後に説明する定理によれば、秘密ランダム列プロトコルで本来より O(log n) のビットを追加することで公開ランダム列プロトコルをシミュレート可能である。 乱択複雑性とは単にこのようなプロトコルで交換するビット数として定義される。 乱択プロトコルを片側誤りを持つような形式で定義することもでき、それに従って複雑性も同様に定義される。
※この「乱択通信複雑性」の解説は、「通信複雑性」の解説の一部です。
「乱択通信複雑性」を含む「通信複雑性」の記事については、「通信複雑性」の概要を参照ください。
- 乱択通信複雑性のページへのリンク
