RE（複雑さ）

複雑度クラス

計算可能性理論と計算複雑性理論において、RE（再帰的列挙可能）とは、チューリングマシンによって有限時間内に「はい」の答えが検証できる決定問題のクラスである。 ^[1]非公式には、問題インスタンスに対する答えが「はい」である場合、有限時間かけてそれを決定する何らかの手順が存在し、この手順は真の答えが「いいえ」であるときに誤って「はい」と報告することはないことを意味する。しかし、真の答えが「いいえ」である場合、手順は停止する必要はなく、「いいえ」の場合には「無限ループ」に入る可能性がある。このような手順は、決定問題に対する完全な解として定義されるアルゴリズムと区別するために、セミアルゴリズムと呼ばれることがある。 ^[2]

同様に、共再帰とは、再帰的言語の補集合であるすべての言語の集合です。ある意味では、共再帰には、帰属が有限の時間で反証できる言語が含まれますが、帰属の証明には永遠にかかる可能性があります。

同等の定義

同様に、RE は、チューリングマシンがすべての「はい」のインスタンスを一つずつ列挙できる決定問題のクラスです（これが「列挙可能」の意味です）。RE の各要素は再帰的に列挙可能な集合であり、したがってディオファントス集合です。

これが等価であることを示すために、もし受け入れ可能な入力をすべて列挙する機械があるとすれば、文字列を入力する別の機械は、その文字列が列挙されている場合に実行し、受け入れることができる点に注目してください。逆に、ある言語で入力されたときに受け入れる機械があるとすれば、別の機械は、入力ごとにのシミュレーションを交互に実行し、受け入れ可能な文字列を出力することで、その言語のすべての文字列を列挙することができます（入力とステップの順序付きペアは可算数個存在するため、最終的にはすべての実行ステップに到達する実行順序が存在します）。 $E$ $E$ $M$ $M$

他のクラスとの関係

再帰言語の集合（R ）は、再帰言語と共再帰言語の両方のサブセットです。^[3]実際、再帰言語はこれら2つのクラスの共通部分です。なぜなら、認識器と共認識器が存在するあらゆる問題は、結果が得られるまでそれらを単純に交互に並べるだけで解決できるからです。したがって、

{\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}

。

逆に、 REにもco-REにも属さない言語の集合はNRNCと呼ばれます。NRNCとは、有限時間内に帰属も非帰属も証明できない言語の集合であり、 REにもco-REにも属さない他のすべての言語を含みます。つまり、以下のようになります。

{\mbox{NRNC}}={\mbox{ALL}}-({\mbox{RE}}\cup {\mbox{co-RE}})

。

これらの問題は決定不可能であるだけでなく、それら問題もそれらの補問題も再帰的に列挙可能ではありません。

2020年1月、REがMIP*クラス（古典的な検証者がエンタングルメントを共有する複数の強力な量子証明者と対話するクラス）と同等であるという証明がプレプリントで発表されました^。[4] 2021年11月に、まだ完全にレビューされていないが、改訂された証明がCommunications of the ACMに掲載されました。この証明は、コンヌ埋め込み問題とツィレルソンの問題が誤りであることを示唆しています。^[5]

再完了

RE完全とは、 REについて完全な決定問題の集合です。ある意味で、これらは「最も難しい」再帰的に列挙可能な問題です。一般的に、使用される縮約には、多対一縮約でなければならないという制約以外には、何の制約もありません。

再完全問題の例:

停止問題: 有限の入力を与えられたプログラムが実行を終了するか、永久に実行されるか。
ライスの定理によれば、部分再帰関数の集合の任意の非自明な部分集合におけるaの帰属を決定することはRE困難である。集合が再帰的に可算である限り、これは完全となる。
ジョン・マイヒル（1955）^[6]は、すべての創造集合がRE完全であることを証明した。
群または半群に対する一様文章問題。(実際、いくつかの個々の群に対する文章問題はRE完全です。)
一般的な無制限形式文法における帰属関係の決定。（繰り返しますが、特定の個別文法にはRE完全帰属関係の問題がある。）
第一階論理の妥当性問題。
ポスト対応問題: 文字列のペアのリストが与えられた場合、これらのペアから選択して (繰り返しを許可)、最初の項目 (ペアの) の連結が 2 番目の項目の連結と等しくなるかどうかを判断します。
ディオファントス方程式に整数解があるかどうかを判定します。

共同RE完了

co-RE-completeは、 co-REに対して完全な意思決定問題の集合です。ある意味では、これらは最も困難な再帰的可算問題の補集合と言えます。

共再完了問題の例:

王牌のドミノ問題。
第一階述語論理の満足度問題。

参照

参考文献

^ 複雑性動物園：クラス RE
^ Korfhage, Robert R. (1966). Logic and Algorithms, With Applications to the Computer and Information Sciences . Wiley. p. 89.問題PをデバイスM上で解く場合、その解法は「半アルゴリズム」と呼ばれる。これは、 Pの解（もし存在するならば）が有限回のステップ実行後に現れる場合である。さらに、問題に解がない場合でも、その方法によってデバイスが有限回のステップと停止の後に解を決定できる場合、半アルゴリズムは「アルゴリズム」と呼ばれる。
^ 複雑性動物園：クラス共存RE
^ Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2020). "MIP*=RE". arXiv : 2001.04383 [quant-ph].
^ Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2021年11月). "MIP* = RE". Communications of the ACM . 64 (11): 131– 138. doi : 10.1145/3485628 . S2CID 210165045.
^ Myhill、John (1955)、「クリエイティブセット」、Zeitschrift für Mathematische Logik und Grundlagen der Mathematik、1 (2): 97–108、doi :10.1002/malq.19550010205、MR 0071379 。

[1] 複雑性動物園：クラス RE

[2] Korfhage, Robert R. (1966). Logic and Algorithms, With Applications to the Computer and Information Sciences . Wiley. p. 89.問題PをデバイスM上で解く場合、その解法は「半アルゴリズム」と呼ばれる。これは、 Pの解（もし存在するならば）が有限回のステップ実行後に現れる場合である。さらに、問題に解がない場合でも、その方法によってデバイスが有限回のステップと停止の後に解を決定できる場合、半アルゴリズムは「アルゴリズム」と呼ばれる。

[3] 複雑性動物園：クラス共存RE

[4] Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2020). "MIP*=RE". arXiv : 2001.04383 [quant-ph].

[5] Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2021年11月). "MIP* = RE". Communications of the ACM . 64 (11): 131– 138. doi : 10.1145/3485628 . S2CID 210165045.

[6] Myhill、John (1955)、「クリエイティブセット」、Zeitschrift für Mathematische Logik und Grundlagen der Mathematik、1 (2): 97–108、doi :10.1002/malq.19550010205、MR 0071379 。