RE_(計算複雑性理論)

ウィキペディア

RE (計算複雑性理論)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/10/13 14:48 UTC 版)

計算複雑性理論において、複雑性クラス RE（recursively enumerable）とは、チューリングマシン（Turing machine）で有限時間内に 'yes' という解を得られる決定問題の集合である。逆に解が 'no' であった場合、マシンが停止するかどうかも保証されない。

RE はまた、解が 'yes' であるような問題をチューリングマシンを使ってリストアップ可能な決定問題のクラスでもある。このため 'enumerable'（枚挙可能）と呼ばれる。

解が 'no' の場合に同様の性質となるクラスを Co-RE と呼ぶ。

RE の各要素は帰納的可算集合（recursively enumerable set）である。

他のクラスとの関係

RE は R より厳密に大きいことが知られており、Co-RE とは厳密に等しくないことが知られている。これらには次のような関係がある。

${\textbf {R}}={\textbf {RE}}\cap {\textbf {Co-RE}}$ この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

Weblio日本語例文用例辞書

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

• REM睡眠中の脳波は起きている時と同じ脳波であり、夢を見るステージです。
• 昔のフランス語のMARBREは異化作用により英語のMARBLEとなった
• REビジネスという事業
• COREという,米国のコンピューターグラフィックスの規格
• 新顔の中では，KICK THE CAN CREW，w-inds.そしてRAG FAIRが白組(男性チーム)での出場だ。
• トヨタの別の展示車に｢i-REAL(アイ リアル)｣がある。
• 愛知県常(とこ)滑(なめ)市(し)にある中部国際空港(セントレア)が，トヨタ自動車の１人乗り３輪自動車｢i-REAL(アイ リアル)｣を４台入手した。
• トヨタは2007年に東京モーターショーで｢未来のクルマ｣，i-REALを初めて展示した。
• i-REALは最高時速30キロで移動できる。
• アメリカ航空宇宙局(NASA)は先日，2016年に無人宇宙探査機｢OSIRIS-REx(オシリス・レックス)｣を打ち上げると発表した。
• OSIRIS-RExのミッションは小惑星で試料を採取して地球に持ち帰ることだ。
• ４年間飛行した後，OSIRIS-RExは｢1999 RQ36｣と名づけられた小惑星に接近し，６か月かけて地表を調査する。
• 試料の採取場所が決まると，OSIRIS-RExはロボットアームを伸ばし，地表の物質を50グラム以上カプセルに採取する。
• 下級生がカードを掲げて｢DREAM｣の文字を作っています。
• JR東日本とその子会社である日本レストランエンタプライズ(NRE)が，３月１日にパリのリヨン駅で駅弁の販売を開始した。