|
|
| 1行目: |
1行目: |
| − | [[計算複雑性理論]]において、[[複雑性クラス]] '''RE'''（recursively enumerable）とは、[[チューリングマシン]]（Turing machine）で有限時間内に 'yes' という解を得られる[[決定問題]]の集合である。逆に解が 'no' であった場合、マシンが停止するかどうかも保証されない。
| + | {{テンプレート:20180815sk}} |
| − | | |
| − | '''RE''' はまた、解が 'yes' であるような問題をチューリングマシンを使ってリストアップ可能な決定問題のクラスでもある。このため 'enumerable'（枚挙可能）と呼ばれる。
| |
| − | | |
| − | 解が 'no' の場合に同様の性質となるクラスを Co-'''RE''' と呼ぶ。
| |
| − | | |
| − | '''RE''' の各要素は[[帰納的可算集合]]（recursively enumerable set）である。
| |
| − | | |
| − | == 他のクラスとの関係 ==
| |
| − | '''RE''' は '''[[R (計算複雑性理論)|R]]''' より厳密に大きいことが知られており、Co-'''RE''' とは厳密に等しくないことが知られている。これらには次のような関係がある。
| |
| − | :<math>\textbf{R} = \textbf{RE}\cap\textbf{Co-RE} </math>
| |
| − | | |
| − | == 外部リンク ==
| |
| − | * [https://complexityzoo.uwaterloo.ca/Complexity_Zoo:R#re Complexity Zoo: Class RE].
| |
| − | {{Computer-stub}}
| |
| − | | |
| − | {{複雑性クラス}}
| |
| − | | |
| − | [[Category:計算複雑性理論]]
| |
| − | [[Category:数学に関する記事]]
| |