BPP
BPP（Wikipedia）
そのアルゴリズムは、解がYESのときもNOのときも最大で1/3の確率で間違った答えを返す。
定義の1/3というのは、0以上1/2未満の間の入力と独立な定数で任意である。そして、その定数が変化しても、BPPは変化しない。これは、そのアルゴリズムを複数回実行したとき、解の多数派が誤りであることが指数関数的に減少することによる。
多数決が常に正解であるためには，個々の試行が1/2以上の確率で正しい選択をしなければならんということか．民主主義政治が正しい選択をするためには，個人は1/2以上の確率で正しい選択をしなければならないということか．
直感的にはそう理解できるのだけれど，現実には隣のおっさんの言ってることが1/2以上の確率で正しいとは思えない場合も多々あるのが困ったところだ．
MiniDiary
のどが痛い
風邪が絶賛進行中．酒飲んで寝るわ．
| 投稿者 | CASPAR003 |
| 投稿時刻 | 23:57 |
| カテゴリー | 雑記 |
| コメント | 0 件 |
| トラックバック | 0 件 |
| 記事へのリンク | http://www.caspar003.info/delta/archive/2013/01/11/2357.html |
コメント
- 投稿者
トラックバック
- トラックバック
