ラスベガス法

ラスベガス法の概要

ラスベガス法は、正しい解を必ず返す特性を持つ乱択アルゴリズムです。この手法では、解が見つからない場合に失敗を通知し、正しい解を返す際には必ずその解が正確であるという点が重要です。具体的には、解が「はい」の場合は間違えることはなく、間違った解を提供することがありません。

このアルゴリズムは、計算に使用するリソース量に賭ける形で実行されます。つまり、正しい解を得るために使う時間やリソースにおいて、リスクや不確実性が存在します。平均実行時間が入力の長さに対して多項式的な関数に収束する場合、このラスベガス法は効率的（efficient）であるといえます。

ラスベガス法の実例

簡単な例として、乱択化されたクイックソートを挙げることができます。このアルゴリズムでは、ピボットとなる値をランダムに選択することでソートを行います。結果として、ソート自体は常に正確であり、解が信頼できるものとなります。このように、入力に対するランダム性を導入することで、プロセス全体が効果的に運営されます。

ラスベガス法を用いる際には、一般的に実行時間の上限が設定されることが多いです。これは、アルゴリズムがいつまでも実行され続けることを防ぐための手段として考えられます。

複雑性クラスとラスベガス法

平均実行時間が多項式的な時間になるようなラスベガス法を持つ決定問題の複雑性クラスは「ZPP（Zero-error Probabilistic Polynomial Time）」と呼ばれます。このクラスは、以下のような特性を持つことが知られています：

• - ZPP = RP ∩ co-RP。

ここでのRPクラスとは、多項式時間で実行される乱択アルゴリズムを含む決定問題の集まりです。解が「いいえ」となった場合には必ず正しい結果が得られるものの、解が「はい」の場合には誤った答えを返す可能性があります。

このようなアルゴリズムが、ある問題とその補問題（解が「はい」と「いいえ」が逆にとなる場合）について併用されることで、高い確率で誤りのない解を得られるのです。これがラスベガス法の効率的な構築方法の一つでもあります。ただし、この手法には最悪の場合の実行時間を明確に定義する上限がないことには注意が必要です。

モンテカルロ法との関係

ラスベガス法は、実行を適切なタイミングで中断することによりモンテカルロ法へと変換することも可能です。モンテカルロ法は、リソースに制限がある中で、解が必ずしも完全に正しいとは限らないという特性を持つアルゴリズムです。モンテカルロ法では、解が間違っている可能性を考慮しながら、結果の信頼性を向上させます。

まとめ

ラスベガス法は、解の正確性を重視した効率的な乱択アルゴリズムであり、さまざまな複雑性クラスと強く関連しています。乱択アルゴリズムの世界は広く、別の手法との接続性も高いため、今後の研究や技術の進歩に期待が寄せられています。

もう一度検索