決定問題（計算におけるイエス・ノー問題）

形式化

形式的には、決定問題は有効な入力の領域と、各入力を真（イエス）または偽（ノー）に写す述語を定める。決定手続きとは、任意の有効な入力が与えられたとき、停止して正しいイエス・ノーの答えを返す有効なアルゴリズムである。このような手続きが存在する問題は、決定可能または計算可能と呼ばれる。すべての入力について述語を決定できるアルゴリズムが存在しない場合、その問題は決定不能である。関連する概念に半決定可能性（再帰的可算性）がある。これは、肯定的なインスタンスについては停止して受理するが、否定的なインスタンスについては停止しないことがあるアルゴリズムが存在することをいう。

代表的な例

• 停止問題 — 与えられたプログラムが与えられた入力に対して停止するかを判定する問題であり、古典的な決定不能問題である。
• ブール充足可能性問題（SAT） — ブール式がそれを充足する代入をもつかを判定する問題である。SATは計算複雑性理論の中心的問題であり、最初に知られたNP完全決定問題である。
• グラフ連結性およびその他の基本的なグラフの性質 — 通常は決定可能であり、多くの場合、多項式時間アルゴリズムで効率よく解ける。
• 素数判定（決定形式） — 整数が素数であるかを判定する問題である。決定可能であり、実用上も効率的なアルゴリズムが知られている。
• 一階述語論理の妥当性 — 一階述語論理における妥当性は一般には決定不能であり、これはヒルベルトの決定問題に対する重要な否定的解答となった。

帰着と完全性

決定問題は、一方の問題のインスタンスをイエス・ノーの答えを保存しながら他方の問題のインスタンスへ変換する帰着によって比較される。多対一（写像）帰着とチューリング帰着は、標準的な二つの概念である。帰着によって困難性と完全性を定義できる。ある問題が計算量クラスに属し、そのクラス内のすべての問題がその問題へ帰着できるとき、その問題はそのクラスに対して完全である。たとえばNP完全問題とは、NPのすべての問題が多項式時間多対一帰着によって帰着できる決定問題である。

決定と探索

計算課題の中には、決定問題（そのようなものは存在するか）よりも、探索問題（ある性質をもつ対象を見つける）として自然に表現されるものがある。多くの探索問題には対応する決定版があり、両者の定式化は密接に関係している。効率的な決定手続きはしばしば探索を導くために利用でき、その逆も成り立つ。しかし、計算量による分類や帰着の存在は、定式化によって異なることがある。

実践的・理論的意義

決定問題は、アルゴリズム設計、計算量の境界、不可能性の証明について考察するための、単純で統一的な枠組みを提供する。これは自動推論、充足可能性判定、形式検証、および計算量理論に基づく課題の分類に対する現代的な手法の基盤となっている。どの決定問題が決定可能または扱いやすいかを理解することは、計算の限界を明らかにし、検証、暗号、人工知能で用いられるソフトウェアツールの設計に役立つ。

参考文献・関連資料

入門的な解説は、通常、計算可能性理論および計算複雑性に関する教科書や概説書に見られる。決定不能性の哲学的・歴史的背景については、ヒルベルトの問題と決定問題に関する資料を参照できる。帰着とクラスの詳しい説明については、NP完全性や空間量制限クラスの標準的な解説が参照される。また、補完的な視点として、決定可能性の入門や集合への所属に関する問題の解説も参照されたい。