ラスベガス法

ウィキペディア

ラスベガス法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/16 23:27 UTC 版)

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Las Vegas algorithm|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

ラスベガス法（ラスベガスほう、英: Las Vegas algorithm^{[注釈 1]}）は、間違った解を返さない乱択アルゴリズムを指す^[2]。すなわち、解を返すときは常に正しく、正しい解が求められない場合は失敗を通知する。換言すれば、ラスベガス法は答え（解）については賭けをせず、計算に使用するリソース量についてのみ賭けをする。さらに平均実行時間が入力長の多項式関数で押さられるようなラスベガス法は効率的^{[訳語疑問点]}(efficient)であるという^[3]。ラスベガス法の単純な例にランダム化されたクイックソートがある^[4]。ピボット値をランダムに選択するクイックソートではソート結果は常に正しい。一般に無作為な情報に対してラスベガス法を使う際には、定義上、実行時間の上限を設けることが多い。

複雑性クラス

平均実行時間が多項式時間となるラスベガス法をもつ決定問題の複雑性クラスを ZPP と呼ぶ^[5]。

次のような性質がある^[6]。

${\displaystyle \mathbf {ZPP} =\mathbf {RP} \cap {\text{co-}}\mathbf {RP} .}$