RE (計算複雑性理論)

計算複雑性理論におけるREクラステイ

計算複雑性理論は、問題の解決にかかる計算資源の量を研究する分野であり、その中で特に重要な役割を果たすのが複雑性クラスRE（再帰的可算集合）です。このクラスは、特定の条件を満たす決定問題の集合として定義されます。具体的に言うと、REはチューリングマシンを利用して、有限の時間内に'yes'という解を得ることができる問題を含んでいます。

RE クラスの特性

REに属する場合、問題の解が'yes'であるかはすぐに確認できますが、もし解が'no'であった場合、チューリングマシンが停止するかどうかは保証がありません。これは、ある意味でREのダイナミクスが不確実であることを意味しています。REは、解が'yes'である問題をチューリングマシンを用いて列挙可能であることから「enumerable（枚挙可能）」と名付けられています。

一方、'no'の解に関しては同様の特性を持つクラスがあります。それがCo-REです。Co-REは、解が'no'である問題を扱ったクラスであり、たとえばそのような問題がどのように取り扱われるかに関しても研究が進められています。

REと他のクラスとの関係

計算理論の中でREは、他の複雑性クラスとの関係においても重要です。特に、REクラスはRクラスよりも厳密に大きいと知られています。Rクラスは、決定性がある問題の集合を示しており、REとCo-REが交わった部分集合として定義できます。このため、次のように表現されます。

$$
\textbf{R} = \textbf{RE} \cap \textbf{Co-RE}
$$

これは、RクラスがREとCo-REの両方に属する問題の全てを含むことを示しています。REとCo-REは、いずれも帰納的可算として重要ですが、両者が厳密に等価であることはありません。この違いが、問題の解決における計算資源の可用性に影響を与えるため、興味深い研究が続けられています。

まとめ

計算複雑性理論におけるREクラスは、決定問題の一つの側面を表す重要な概念であり、チューリングマシンとの関係を深く理解することで、計算の本質に迫ることができます。解が'yes'の場合には計算が可能である一方、'no'の場合の不確実性を含むREは、計算理論の研究において重要な役割を果たします。このように、REクラス及びその関連クラスであるCo-REは、計算可能性の枠組みを理解するための鍵となる要素です。

さらに興味を持たれた方は、Complexity Zooなどの外部リンクを参照するのもおすすめです。

もう一度検索