RP_(計算複雑性理論)とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > RP_(計算複雑性理論)の意味・解説 

RP (計算複雑性理論)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2020/04/14 03:55 UTC 版)

ナビゲーションに移動 検索に移動

計算複雑性理論におけるRP(randomized polynomial time)とは、以下の3つの属性を持つ確率的チューリング機械で解ける問題の複雑性クラスである。

RPアルゴリズム(1回試行)
生成される解
正解 YES NO
YES ≥½ ≤½
NO 0 1
RPアルゴリズム(n回試行)
生成される解
正解 YES NO
YES ≥1-½n ≤½n
NO 0 1
Co-RPアルゴリズム(1回試行)
生成される解
正解 YES NO
YES 1 0
NO ≤½ ≥½
  • 入力長に対して常に多項式時間かかる。
  • 正解が NO である場合、常に NO を返す。
  • 正解が YES である場合、確率 ½ 以上で YES を返す(そうでない場合、NO を返す)。

換言すれば、そのアルゴリズムは、実行中に完全に無作為なコインを投げているようなものである。このアルゴリズムが YES を返すのは、実際の答えが YES であるときだけである。したがって、アルゴリズムが停止して YES を生成した場合、正解は必ず YES である。しかし、NO を返して停止する場合、実際の答えが何であるかはわからない。つまり、NO を返したとき、それは間違っている可能性がある。

この複雑性クラスを R と呼ぶこともあるが、一般に R と言えば帰納言語のクラスの名称として使われている。

正解が YES であるとき、このアルゴリズムを n 回試行し、各試行には確率論的独立性があるとき、YES が少なくとも 1回返される確率は 1 - ½n 以上である。従って、100回試行すれば回答が間違っている確率は、宇宙線がコンピュータのメモリの内容を破壊して計算結果を間違う可能性よりも低くなる。従って、乱数発生源があれば、RP に属するアルゴリズムの多くは極めて実用的となる。

½ という割合は実際には任意の割合でよい。½ が 0 より大きく 1 より小さい任意の割合でありさえすれば、RP に属する問題の性質は変わらない。この定数はアルゴリズムの入力の内容や長さとは無関係である。

関連する複雑性クラス

RP の定義によれば、YES という解は常に正しく、NO という解はおおむね正しい。Co-RP クラスも同様に定義でき、NO という解が常に正しく、YES という解がおおむね正しい。換言すれば、Co-RP に相当するチューリング機械は YES となるべき入力は常に受理するが、NO となるべき入力は受理するか不受理かのどちらかとなる。BPP クラスは正解が YES であっても NO であっても間違う可能性のあるアルゴリズムに相当する。RP と Co-RP の積集合に相当するクラスを ZPP と呼ぶ。RPR と呼ぶように、Co-RP を Co-R と呼ぶことがある。

PおよびNPとの関係

PRP の部分集合であり、RPNP の部分集合である。同様に、P は Co-RP の部分集合であり、Co-RPCo-NP の部分集合である。これらの包含関係が真部分集合の関係であるかどうかは未だわかっていない。しかし、一般に PRP または RPNP であろうと考えられており、そうでないと P = NP ということになってしまい、これは一般には偽と考えられている(P≠NP予想)。RP = Co-RP であるかどうかも未だ明らかになっていないし、RPNP と Co-NP の積集合の部分集合かどうかも明らかでない。

Co-RP に属する問題のうち、P に属さないと思われている問題の例として、整数に関する多変量計算式がゼロ多項式かどうかの判定問題がある。例えば、"x*x - y*y - (x+y)*(x-y)" はゼロ多項式だが、"x*x + y*y" はゼロ多項式ではない。

場合によってはより便利と思われる RP の定式化として、少なくともある(入力長に依らない)一定の割合の計算経路群が受理する場合に限って機械全体としてその入力を受理する非決定性チューリング機械が認識できる問題の集合という定義がある。一方、NP は少なくとも一つの計算経路だけが受理すればよいのであって、その割合は指数関数的に小さい。このように定式化すると、RPNP の部分集合であることがより明確化される。

関連項目


「RP (計算複雑性理論)」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「RP_(計算複雑性理論)」の関連用語

RP_(計算複雑性理論)のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



RP_(計算複雑性理論)のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのRP (計算複雑性理論) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS