検索問題

計算複雑性理論および計算可能性理論において、探索問題とは、与えられた入力値に対して許容可能な解が存在する場合に、その解を見つける計算問題である。実際、探索問題は、xRyが「y はxが与えられたときの許容可能な解である」場合に限り成り立つ二項関係Rによって指定される。^{[注 1 ]}探索問題は、グラフ理論や組み合わせ最適化において頻繁に発生する。例えば、与えられた無向グラフにおけるマッチング、オプションのクリーク、安定集合の探索などである。

アルゴリズムは、入力値xに対して、適切な解答yが存在する場合にはそれを返し、存在しない場合には適切な出力（例えば、解答が存在しないxに対しては「見つかりませんでした」 ）を返す場合に、探索問題を解決すると言われます。

PlanetMathは問題を次のように定義しています。^{[ 1 ]}

もし${\displaystyle R}$は、次のような二項関係である。$\displaystyle \operatorname {field} (R)\subseteq \Gamma ^{+}}$そして${\displaystyle T}$はチューリングマシンである、${\displaystyle T}$計算する${\displaystyle f}$もし: ^{[注2 ]}

• もし${\displaystyle x}$それは、${\displaystyle y}$そのため${\displaystyle R(x,y)}$それから${\displaystyle T}$受け入れる${\displaystyle x}$出力付き${\displaystyle z}$そのため${\displaystyle R(x,z)}$（複数存在する可能性があります）${\displaystyle y}$、 そして${\displaystyle T}$そのうちの1つを見つけるだけでよい）
• もし${\displaystyle x}$それは、${\displaystyle y}$そのため${\displaystyle R(x,y)}$それから${\displaystyle T}$拒否${\displaystyle x}$。

部分関数のグラフは二項関係であることに注意してください。${\displaystyle T}$部分関数を計算する場合、可能な出力は最大で1つです。

1${\displaystyle R}$探索問題とみなすことができ、チューリングマシンは${\displaystyle R}$もそれを解決すると言われています。すべての探索問題には対応する決定問題があります。${\displaystyle L(R)=\{x\mid \exists yR(x,y)\}.}$

この定義は、複数の文字列を1つの文字列に圧縮できる適切なエンコーディング（例えば、区切り文字で連続して列挙するなど）によって、 n項関係に一般化できます。

• 無制限探索演算子
• 意思決定問題
• 最適化問題
• 計数問題（複雑性）
• 機能の問題
• 検索ゲーム

この記事は、 PlanetMathの探索問題から得た資料を組み込んでおり、クリエイティブ・コモンズ表示-継承ライセンスの下でライセンスされています。