決定的アルゴリズムの問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/09 08:27 UTC 版)
「決定的アルゴリズム」の記事における「決定的アルゴリズムの問題」の解説
しかし、ある種の問題では決定的アルゴリズムを発見するのが困難である。例えば、ある数が素数であるかを判定する単純で効率的な乱択アルゴリズムが存在し、判定を間違う可能性は極めて小さい（ミラー-ラビン素数判定法）。そのようなアルゴリズムは1970年代から知られているが、同様の問題についての決定的アルゴリズムはそれに比較するとあまりにも時間がかかる。 実用的にも重要な問題が多く属するNP完全問題は、非決定性チューリング機械を使えば高速に解くことができるが、効率的な決定的アルゴリズムは見つかっていない。そのため、現状では近似解を求めたり、特殊な条件を付与して解を求めるしかない。 別の問題として、予測不可能性が要求されることもあるということが挙げられる。例えば、ブラックジャックをコンピュータゲームとして実装した場合、デッキを擬似乱数を使ってシャッフルすることになる。プレイヤーがその擬似乱数の性質を知っていれば、カードがどういう順番になっているかが分かってしまう。実際、Reliable Software Technologies の Software Security Group が ASF Software, Inc. のポーカーゲームについてそのような解析を行った。同様の問題は暗号理論にもあり、秘密鍵は擬似乱数を使って生成されることが多い。このような問題を防ぐものとして暗号論的擬似乱数生成器 (CSPRNG) が使われる。
※この「決定的アルゴリズムの問題」の解説は、「決定的アルゴリズム」の解説の一部です。
「決定的アルゴリズムの問題」を含む「決定的アルゴリズム」の記事については、「決定的アルゴリズム」の概要を参照ください。
- 決定的アルゴリズムの問題のページへのリンク
