意思決定問題

計算可能性理論および計算複雑性理論において、決定問題とは、入力値の集合に対してイエス・ノーの質問として定式化できる計算問題のことである。決定問題の一例としては、与えられた自然数が素数であるかどうかを判定することが挙げられる。別の例としては、「2つの数xとyが与えられたとき、xはyを割り切るか？」という問題がある。

決定問題に対する決定手順とは、すべての入力に対してイエス・ノーの質問に答えるアルゴリズム的方法であり、決定手順が存在する場合、決定問題は決定可能であると呼ばれます。たとえば、「2 つの数xとyが与えられたとき、x はy を割り切るか？」という決定問題は、 x がy を割り切るかどうか、そしてそれに応じて正しい答え ( YESまたはNO)を決定する手順を示す長除法と呼ばれる決定手順が存在するため、決定可能です。数学における最も重要な問題の中には、停止問題のように決定不可能なものもあります。

計算複雑性理論の分野では、決定可能な決定問題を、その解決の難しさによって分類します。ここでいう「難しさ」とは、特定の問題に対して最も効率的なアルゴリズムが必要とする計算リソースの量を指します。一方、再帰理論の分野では、決定不可能な決定問題をチューリング度によって分類します。チューリング度とは、あらゆる解に内在する計算不可能性の尺度です。

決定問題とは、出力（与えられた入力に対するイエス・ノーの質問への回答）がYESとなるすべての入力の形式言語のことである。^{[注1 ]}

• これらの入力は自然数でも構いませんが、バイナリ文字列や他のアルファベット上の文字列など、他の種類の値でも構いません。

• 例えば、すべての入力がアルファベットでエンコードできる場合${\displaystyle \{0,1\}}$すると、決定問題は部分集合となる。${\displaystyle L\subseteq \{0,1\}^{*}}$[^{注1 ]}

• 別の例として、ゲーデル数化などの符号化方式を用いると、任意の文字列を自然数に符号化することができ、それによって決定問題を自然数の部分集合として定義できます。したがって、決定問題の決定手順は、自然数の部分集合の特性関数を計算することになります。

決定可能な決定問題の典型的な例は、素数の集合である。与えられた自然数が素数であるかどうかは、考えられるすべての非自明な因数をテストすることで効果的に判定できる。素数判定にはもっと効率的な手順が知られているが、有効な手順が存在するだけで決定可能性が確立される。

• 決定問題は、答えがYESとなる入力の集合が再帰的な集合である場合に、決定可能または効果的に解決可能である。^{[注2 ]}
• 決定問題は、答えがYESとなる入力の集合が再帰的に列挙可能な集合である場合、部分的に決定可能、半決定可能、解決可能、または証明可能である。

決定できない問題は決定不能問題と呼ばれ、つまり、それを解決するアルゴリズム（効率的なものか否かを問わず）を作成することはできません。停止問題は重要な決定不能問題です。その他の例については、決定不能問題の一覧を参照してください。

決定問題は、多対一還元可能性に基づいて順序付けられ、多項式時間還元などの実行可能な還元と関連付けられる。決定問題Pは、決定問題の集合Sの要素であり、Sのすべての問題がPに還元できる場合、決定問題の集合 S に対して完全であると言われる。完全な決定問題は、計算複雑性理論において、決定問題の複雑性クラスを特徴付けるために用いられる。例えば、ブール充足可能性問題は、多項式時間還元可能性の下で、決定問題のクラスNPに対して完全である。

意思決定問題は関数問題と密接に関連しており、関数問題の答えは単純な「はい」または「いいえ」よりも複雑な場合があります。対応する関数問題の例としては、「2つの数xとyが与えられたとき、 xをyで割った値は何か？」というものがあります。

関数問題とは、部分関数fから構成される問題であり、非公式な意味での「問題」は、 f が定義されている入力値に対してfの値を計算することである。

すべての関数問題は決定問題に変換できます。決定問題は、関連する関数のグラフです。（関数fのグラフは、 f ( x ) = yとなるペア ( x , y )の集合です。）この決定問題が効果的に解けるのであれば、関数問題も同様に解けるはずです。ただし、この還元は計算複雑性を尊重しません。たとえば、関数が多項式時間で計算できない場合でも、関数のグラフが多項式時間で決定可能（この場合、実行時間はペア ( x , y ) の関数として計算されます）になることがあります（この場合、実行時間はxのみの関数として計算されます）。関数f ( x ) = 2x^はこの性質を持ちます。

すべての決定問題は、その決定問題に関連付けられた集合の特性関数を計算する関数問題に変換できます。この関数が計算可能であれば、関連する決定問題は決定可能です。ただし、この還元は、計算複雑性で用いられる標準的な還元（多項式時間多対一還元と呼ばれることもあります）よりも寛容です。例えば、NP完全問題とその補集合であるco-NP完全問題の特性関数の複雑性は、 典型的な計算モデルでは基礎となる決定問題が同等とみなされない場合でも、まったく同じです。

意思決定問題では、各入力に対して正解が1つしか存在しないのに対し、最適化問題は、特定の入力に対する最適な答えを見つけることを目的としている。最適化問題は、巡回セールスマン問題や線形計画法における多くの問題など、多くの応用分野で自然に発生する。

関数問題や最適化問題は、出力が与えられた値と等しいか、それ以下か、あるいはそれ以下かという問題を考慮することで、しばしば決定問題に変換されます。これにより、対応する決定問題の複雑さを研究することが可能になり、多くの場合、元の関数問題や最適化問題は、対応する決定問題を解くことで解決できます。例えば、巡回セールスマン問題では、最適化問題は最小の重みを持つ巡回路を作成することです。関連する決定問題は、各Nについて、グラフにNより重みの小さい巡回路が存在するかどうかを判定することです。この決定問題を繰り返し解くことで、巡回路の最小の重みを見つけることができます。

意思決定問題の理論は非常に発展しているため、複雑性理論の研究はこれまで主に意思決定問題に焦点を当ててきた。最適化問題自体は、計算可能性理論だけでなく、オペレーションズリサーチなどの分野においても依然として関心を集めている。

• すべて（複雑性）
• 計算上の問題
• 計数問題（複雑性）
• 決定可能性（論理）–論理式が論理理論の帰結であるかどうかを判定する問題。
• フォーマルな言葉
• 検索問題
• 文章問題（数学）

• コゼン、DC (2012)。オートマトンと計算可能性。スプリンガー。ISBN 978-1-4612-1844-9。
• ハートリー、ロジャース・ジュニア（1987）。再帰関数と有効計算可能性の理論。MIT Press。ISBN 978-0-262-68052-3。
• Sipser, M. (2020).計算理論入門. Cengage Learning. ISBN 978-0-357-67058-3。
• ソアレ、ロバート・I. (1987).再帰的に列挙可能な集合と次数. スプリンガー. ISBN 0-387-15299-7。
• ダニエル・クローニング;ストリッチマン、オファー(2008 年 5 月 23 日)。決定手順。スプリンガー。ISBN 978-3-540-74104-6。
• ブラッドリー、アーロン；マンナ、ゾハール（2007年9月3日）。計算の微積分。シュプリンガー。ISBN 978-3-540-74112-1。