決定問題

決定問題とは

決定問題（decision problem）とは、計算理論における基本的な問題形式の一つで、与えられた入力に対して「はい」（受理）または「いいえ」（拒絶）のいずれかの二択で答える問題のことです。判定問題とも呼ばれます。これは、入力として与えられた情報が特定の条件を満たすかどうかを判断するもので、その結果は必ず二つの状態のいずれかに分類されます。

形式的な定義

決定問題は、数学的には以下のように定義されます。

文字列の集合 \( \{0, 1\}^ \) （0と1からなる全ての可能な文字列の集合）またはその部分集合から、 \( \{0, 1\} \) （0または1）への写像として表現できます。ここで、0は「いいえ」（拒絶）を、1は「はい」（受理）を表します。つまり、与えられた入力文字列に対して、ある条件を満たす場合は1を、そうでない場合は0を返す関数として捉えることができます。

具体例

決定問題の具体的な例として、以下のようなものが挙げられます。

充足可能性問題（SAT）：与えられた命題論理式に対して、その論理式を真にするような真理値の割り当てが存在するかどうかを判定する問題です。もしそのような割り当てが存在すれば「はい」、存在しなければ「いいえ」となります。
素数判定問題：与えられた自然数が素数であるかどうかを判定する問題です。素数であれば「はい」、そうでなければ「いいえ」となります。

これらの例のように、決定問題は入力に対する単純な「はい」「いいえ」の回答を求める問題であり、複雑な計算結果や具体的な値を必要としません。

関数問題との違い

決定問題と対比される問題形式として、関数問題（function problem）があります。関数問題は、入力に対して具体的な値を返すことを目的とします。例えば、以下のような問題が関数問題に該当します。

充足可能性問題の解の出力：与えられた命題論理式を真にする真理値割り当てを具体的に出力する。
素因数分解：与えられた自然数を素因数の積として分解する。

決定問題が「存在するかどうか」という二択の判断を行うのに対し、関数問題は「具体的にどのような値か」を求める点が異なります。

計算理論における重要性

決定問題は、計算理論において重要な役割を果たします。その理由として、以下の点が挙げられます。

数学的な扱いやすさ：決定問題は、形式的に定義しやすく、数学的な分析や証明が比較的容易です。
出力にかかる時間の考慮が不要：出力が「はい」か「いいえ」の二択であるため、具体的な出力値を求めるためにかかる時間を考慮する必要がありません。これにより、計算時間の複雑さを評価する際に扱いやすくなります。
問題の一般化：多くの計算問題を決定問題に変換して考えることで、様々な問題を統一的に扱うことが可能になります。

これらの理由から、決定問題は計算複雑性理論において、問題の難しさや計算可能性を議論するための基本的な枠組みとして用いられます。

関連概念

決定問題に関連する概念として、以下のようなものが挙げられます。

計算複雑性理論：計算問題を解くのに必要な計算資源（時間やメモリなど）の量に関する理論です。決定問題の難しさを分類し、効率的なアルゴリズムが存在するかどうかを研究します。
決定可能性：与えられた問題に対して、必ず有限時間で正しい答えを返すアルゴリズムが存在するかどうかという概念です。決定問題は、決定可能性を議論するための重要な対象となります。

まとめ

決定問題は、計算理論における基本的な問題形式であり、与えられた入力に対して「はい」または「いいえ」で答える二択の問題です。その数学的な扱いやすさと計算時間の複雑さを考慮する上での利便性から、計算理論の研究において重要な役割を果たしています。この概念を理解することは、計算可能性や計算複雑性についての理解を深める上で不可欠です。

もう一度検索