RE（複雑さ）

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

同様に、co-RE は、RE内の言語の補完となるすべての言語の集合です。ある意味では、co-REには、メンバーシップが有限の時間内に反証できる言語が含まれますが、メンバーシップの証明には永遠にかかる可能性があります。

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

これが同等であることを示すには、受け入れられるすべての入力を列挙するマシンがある場合、文字列を受け取る別のマシンが実行して、文字列が列挙されている場合は受け入れることができることに注意してください。逆に、入力が言語である場合にマシンが受け入れる場合、別のマシンは、すべての入力で のシミュレーションをインターリーブし、受け入れられた文字列を出力することで、その言語のすべての文字列を列挙できます (入力とステップの順序付きペアは数え切れないほどあるため、最終的にすべての実行ステップに到達する実行順序があります)。 ${\displaystyle E}$${\displaystyle E}$${\displaystyle M}$${\displaystyle M}$

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

${\displaystyle {\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}}$。

逆に、 REでもco-REでもない言語の集合はNRNCとして知られています。これらは、メンバーシップも非メンバーシップも有限の時間内に証明できない言語の集合であり、 REにもco-REにも属さない他のすべての言語が含まれます。つまり、

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

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

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

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

再完了問題の例:

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

co-RE 完全は、co-REに対して完全な決定問題の集合です。ある意味では、これらは最も困難な再帰的に列挙可能な問題の補完です。

共RE完了問題の例:

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

• クヌース・ベンディックス補完アルゴリズム
• 解決不可能な問題のリスト
• 多態的再帰
• リッシュアルゴリズム
• 半決定可能性