令和5年度 九州大学システム情報科学府
計算中にランダムな選択を行うことで高確率で効率的に正解を得る手法を乱択といい、多くのアルゴリズムで使われている。乱択が効率的に問題を解く上でどれほど本質的なのか（決定的に作った数列を乱数の代りに用いてはダメなのか）、という問は計算量理論の大きなテーマの一つであり、多項式時間計算など幾つかの重要な意味においては未解決である（BPP＝P予想）。この問がどのように定式化され、他の困難さ予想とどのように関わるのか解説する。
キーワード 計算量、多項式時間、乱択、脱乱択、擬乱数生成