1 定義
決定問題は、与えられた対象が特定の条件を満たすかどうかを、「はい」か「いいえ」で答える形式の問題である。数学や計算機科学では、解を数値や構造そのものではなく、真偽の判定として表す点に特徴がある。
この種の問題は、入力が何であるか、どのような規則で判定するか、そしてその判定が機械的に実行できるかによって性質が変わる。理論上はきわめて抽象的だが、実際にはアルゴリズム設計や論理推論の基礎を支える概念として用いられる。
1.1 基本的な定義
基本的には、決定問題とは、ある入力に対して所属の可否を問う問題である。たとえば、ある数が素数かどうか、あるグラフに特定の経路が存在するかどうか、といった問いが該当する。
ここで重要なのは、答えが一意に二値へ整理されることである。結果として、問題の記述は「条件を満たす入力の集合」を定める形に変換される。
1.2 判定形式の特徴
判定形式では、出力が真偽値に限定されるため、問題の構造が比較的明確になる。これにより、アルゴリズムの正しさや計算量を分析しやすくなる。
また、判定問題は他のタイプの問題の基盤としても扱われる。探索や最適化の課題であっても、まず判定版を考えることで理論的な整理が進む場合が多い。
1.3 問題の表現と入力
決定問題は、入力をどのように記述するかで形式が定まる。数、グラフ、式、文字列など、対象に応じて符号化の方法が選ばれる。
この表現の仕方は、問題の本質そのものではないが、計算量や扱いやすさに影響を与える。特に理論計算機科学では、入力を有限長の文字列として扱うことが標準的である。
2 数学的基礎
決定問題は、集合、言語、論理式といった数学的対象と密接に結びついている。これらの対応関係により、問題を形式的に記述し、異なる分野間で共通の枠組みとして扱うことが可能になる。
2.1 集合としての表現
決定問題は、答えが「はい」である入力全体の集合として表せる。逆に言えば、その集合に属するかどうかを調べる作業が決定問題である。
この見方では、問題そのものと集合の記述がほぼ同一視される。したがって、問題の研究は集合の性質を調べることにもつながる。
2.2 言語との対応
決定問題は、形式言語の理論と自然に対応する。入力を文字列として表すとき、「はい」と答える文字列の集合は一つの言語とみなせる。
この対応によって、計算の問題が言語の受理や認識の問題へと置き換えられる。結果として、自動機械や文法の理論と接続しやすくなる。
2.2.1 決定問題と言語
決定問題は、ある言語に文字列が属するかどうかを問う形に整理できる。ここで言語とは、記号列の集合を意味する。
この対応は、理論計算機科学で非常に重要である。多くの計算モデルは、ある言語を受理できるかどうかという観点から比較される。
2.2.2 文字列集合としての見方
文字列集合として捉えると、決定問題は単に入力列の選別問題になる。各入力は有限長の記号列に変換され、判定対象はその集合への所属となる。
この整理により、抽象的な対象でも統一的に扱える。数や図形のような異なる対象が、同じ枠組みで比較可能になる。
2.3 論理式との関係
決定問題は、論理式の真偽判定とも深く関係する。与えられた式がある構造の下で真かどうかを調べる問題は、典型的な決定問題である。
論理との結びつきは、証明論やモデル理論にも及ぶ。とくに、ある性質が論理的に表現できるかどうかは、計算可能性の限界を考えるうえで重要である。
3 計算可能性
決定問題の中心的な論点の一つは、機械的な手続きで必ず正しい答えを得られるかどうかである。これが計算可能性の問題であり、理論計算機科学の基礎をなす。
3.1 計算可能な決定問題
計算可能な決定問題とは、有限時間で正しい判定を行うアルゴリズムが存在する問題である。入力がどのような場合でも、手続きは停止し、答えを返す。
この性質をもつ問題は、原理的には機械による完全な判定が可能である。実用上の効率とは別に、まず解けるかどうかが問われる。
3.2 非計算可能な決定問題
一方で、どのようなアルゴリズムを用いても一般には判定できない問題もある。これらは非計算可能問題と呼ばれ、計算の限界を示す代表例となる。
非計算可能性は、問題が難しいという意味ではなく、そもそも万能の判定法が存在しないことを指す。これは計算理論においてきわめて重要な区別である。
3.2.1 停止問題
停止問題は、与えられたプログラムと入力に対し、そのプログラムが停止するかどうかを問う問題である。これは一般には解けないことが知られている。
この問題は、計算の自己参照や無限挙動を考える際の基本例として扱われる。多くの不可解性の議論は、停止問題を出発点にして展開される。
3.2.2 その他の例
停止問題以外にも、一般的には判定不能な問題が数多く存在する。たとえば、プログラムのある性質がすべての入力で成り立つかを問う問題などがある。
これらの例は、個別の内容は異なっていても、構造的には同様の限界を共有している。すなわち、全域的な決定手続きが存在しない。
3.3 決定手続き
決定手続きとは、ある決定問題に対して答えを与える規則的な方法である。通常はアルゴリズムとして記述される。
手続きが存在するかどうかは、その問題が計算可能かどうかを左右する。さらに、存在する場合でも、効率の良し悪しは別の論点となる。
4 計算複雑性
計算複雑性は、決定問題を解くのに必要な資源を測る分野である。主に時間と空間が対象となり、同じ計算可能問題でも難易度の差が評価される。
4.1 時間計算量
時間計算量は、入力の大きさに応じて必要となる操作回数を表す。決定問題では、判定までにどれだけの段階を要するかが重要になる。
この指標により、実用上扱いやすい問題と、理論的には解けても非現実的な問題が区別される。多項式時間で解けるかどうかは特に重視される。
4.2 空間計算量
空間計算量は、計算中に必要な記憶領域の量を表す。時間と異なり、途中結果をどれだけ保持するかに着目する。
空間が限られていても解ける問題は、計算の資源制約を考えるうえで重要である。時間と空間はしばしば独立した複雑さの尺度として扱われる。
4.3 クラスとの関係
決定問題は、計算量クラスによって分類される。これにより、似た難度や性質をもつ問題群をまとめて考えられる。
クラスの定義は、利用できる時間、空間、非決定性などに基づく。こうした枠組みは、問題間の比較を体系化する。
4.3.1 多項式時間で解ける問題
多項式時間で解ける決定問題は、計算量理論で中心的な位置を占める。一般に、この範囲の問題は比較的扱いやすいと考えられる。
ただし、実際の計算の容易さは次数や定数にも左右されるため、理論上の分類と現場での感覚は必ずしも一致しない。
4.3.2 難しさの比較
決定問題の難しさは、他の問題へどれだけ効率よく変換できるかによって比較される。ある問題が別の問題に還元できるなら、前者の複雑さを後者の観点から評価できる。
この比較法により、個別の問題を孤立して見るのではなく、相互関係の中で位置づけられる。結果として、理論全体の構造が見えやすくなる。
4.4 完全問題と難問
完全問題は、ある複雑性クラスの中でも特に代表的で、そのクラス内の任意の問題から還元される問題である。これらはクラス全体の難しさを象徴する。
一方、難問とは、一般に解法が知られていない、または高い計算資源を要する問題を指す。完全問題は、その代表例としてしばしば挙げられる。
5 他の問題形式との比較
決定問題は、探索問題、最適化問題、数え上げ問題などと対比される。これらはいずれも「何らかの解」を扱うが、求める情報の種類が異なる。
5.1 探索問題との違い
探索問題は、解答の存在だけでなく、実際の解そのものを見つけることを求める。これに対し、決定問題は存在の有無だけを問う。
探索版が解けるなら判定版も解けることが多いが、逆は常に自明ではない。したがって、両者は密接だが同一ではない。
5.2 最適化問題との違い
最適化問題では、可能な解の中から最良のものを求める。たとえば最短路や最大値の計算が該当する。
決定問題は、最適値そのものを返すのではなく、ある基準を満たすかだけを確認する。最適化問題はしばしば、判定問題を基に段階的に扱われる。
5.3 数え上げ問題との違い
数え上げ問題は、条件を満たす解の個数を求める。これは真偽を返す決定問題より、情報量が大きい。
そのため、数え上げは一般により高い難しさを持つことがある。決定問題は、こうしたより豊かな問題形式の基礎層として位置づけられる。
6 決定問題の例
決定問題は、数学、計算機科学、論理学の各分野に数多く現れる。例を通じて、その抽象的な定義が具体的に理解しやすくなる。
6.1 数学における例
数学では、整数が特定の性質をもつかを問う問題が典型例である。素数判定、平方数判定、ある方程式に解があるかどうかなどが含まれる。
これらは、対象が数である点を除けば、いずれも二値の判定として整理できる。数学的性質を機械的に調べる入口として重要である。
6.2 計算機科学における例
計算機科学では、グラフの連結性、文字列の正規表現への適合、プログラムの特定条件の満足などが挙げられる。これらはいずれも入力の性質を問う判定である。
実際のシステムでは、認証、構文解析、検証などに類似の問いが現れる。決定問題は、こうした応用の理論的な土台となる。
6.3 論理における例
論理学では、ある論理式が充足可能か、ある理論から証明可能か、といった問いが決定問題として扱われる。真理値やモデルの存在が判定対象となる。
この分野では、形式体系の性質を調べることが中心である。論理的帰結の判定は、計算理論との接点を作る重要な例である。
7 応用
決定問題の考え方は、理論にとどまらず多くの実践的分野で利用される。特に、明確な可否判定が必要な場面で有効である。
7.1 アルゴリズム設計
アルゴリズム設計では、まず問題を判定形式に落とし込むことがある。これにより、解法の骨格を整理しやすくなる。
判定版が実装可能なら、そこから探索や最適化へ拡張する戦略も取られる。したがって、決定問題は設計手順の出発点になりやすい。
7.2 自動推論
自動推論では、ある命題が導けるかどうかを機械的に調べる。これは、論理式の証明可能性や整合性の確認と関係する。
判定問題として定式化することで、推論機構の性能や限界を明示できる。結果として、証明支援や知識処理の理論的基盤が整う。
7.3 検証と形式手法
検証と形式手法では、システムが仕様を満たすかどうかを判定する。ハードウェアやソフトウェアの安全性確認で特に重要である。
ここでは、仕様を満たすか否かを明確な問いに変換することが鍵となる。決定問題の枠組みは、検証の自動化を支える基本形である。
8 関連概念
決定問題を理解するには、周辺概念との違いを把握することが有用である。特に、決定可能性、半決定可能性、帰着可能性は密接に関係する。
8.1 決定可能性
決定可能性とは、ある問題に対して常に停止し、正しい答えを返す手続きが存在する性質である。決定問題の可解性を表す中心概念である。
この性質があると、問題は理論上完全に扱える。逆に、決定可能でない場合は、一般的な解法は存在しない。
8.2 半決定可能性
半決定可能性は、「はい」の場合にはいずれ確認できるが、「いいえ」の場合には停止しないことがありうる性質である。これは決定可能性より弱い。
この概念は、証明の探索や列挙的な手続きと関係が深い。停止問題のように、片側だけが検出できる場面で現れる。
8.3 帰着可能性
帰着可能性は、ある問題を別の問題へ変換して解くという考え方である。これにより、問題同士の難しさを比較できる。
帰着がうまくいけば、既知の問題の解法や不可能性を利用して、新しい問題の性質を判断できる。計算可能性と複雑性の双方で重要な道具となる。