決定問題

計算可能性理論と計算複雑性理論では、決定問題とは、与えられた入力値に基づいて「はい」か「いいえ」で答えられる計算問題です。決定問題の例としては、与えられた自然数が素数であるかどうかをアルゴリズムを使用して決定することが挙げられます。別の例としては、「2 つの数xとy が与えられたとき、x はy を均等に割り切れるか」という 問題があります。

アルゴリズムの形式で与えられた決定問題を解く方法は、その問題の決定手順と呼ばれます。「2 つの数xとy が与えられたとき、x はy を割り切れるか?」という決定問題に対する決定手順は、x がy を割り切れるかどうかを判断する手順を示します。そのようなアルゴリズムの 1 つが長除法です。余りが 0 の場合、答えは「はい」、そうでない場合は「いいえ」です。アルゴリズムによって解決できる決定問題は、決定可能と呼ばれます。

決定問題は、典型的には、決定可能性、つまり、あるオブジェクトの存在またはその集合内のメンバーシップを決定するための効果的な方法の存在に関する数学的な問題に現れます。数学における最も重要な問題のいくつかは、決定不可能な問題です。

計算複雑性の分野では、決定可能な決定問題を、解決の難しさによって分類します。ここでの「難しさ」は、特定の問題に対する最も効率的なアルゴリズムに必要な計算リソースの観点から説明されます。一方、再帰理論の分野では、決定不可能な決定問題をチューリング次数によって分類します。チューリング次数は、あらゆるソリューションに内在する非計算可能性の尺度です。

意思決定問題とは、無限の入力集合に対する「はい」か「いいえ」の質問です。意思決定問題は、可能な入力の集合と、答えが「はい」となる入力の集合を合わせて定義するのが一般的です。^[1]

これらの入力は自然数にすることもできますが、バイナリ文字列や他のアルファベットの文字列など、他の種類の値にすることもできます。問題が「はい」を返す文字列のサブセットは形式言語であり、多くの場合、決定問題は形式言語として定義されます。

ゲーデル数などのエンコーディングを使用すると、任意の文字列を自然数としてエンコードすることができ、これにより、決定問題を自然数のサブセットとして定義できます。したがって、決定問題のアルゴリズムは、自然数のサブセットの 特性関数を計算することです。

決定可能な決定問題の典型的な例は、素数の集合です。すべての可能な非自明な因数をテストすることで、与えられた自然数が素数であるかどうかを効果的に決定できます。素数かどうかをテストするより効率的な方法が知られていますが、効果的な方法が存在するだけで決定可能性を確立するのに十分です。

決定問題が決定可能または実質的に解決可能であるのは、答えが「はい」となる入力 (または自然数) の集合が再帰的集合である場合です。問題が部分的に決定可能、半決定可能、解決可能、または証明可能であるのは、答えが「はい」となる入力 (または自然数) の集合が再帰的に列挙可能な集合である場合です。決定可能でない問題は決定不可能です。それらの問題に対しては、効率的であろうとなかろうと、それらを解決するアルゴリズムを作成することはできません。

停止問題は重要な決定不能な決定問題です。その他の例については、決定不能な問題のリストを参照してください。

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

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

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

すべての関数の問題は、決定問題に変換できます。決定問題は、関連する関数のグラフにすぎません。(関数fのグラフは、 f ( x ) = yとなるペア ( x、y )の集合です。) この決定問題が効果的に解決可能であれば、関数の問題も同様に解決できます。ただし、この縮小では計算の複雑さは考慮されません。たとえば、関数が多項式時間で計算可能でない (実行時間がxのみの関数として計算される) 場合でも、関数のグラフが多項式時間で決定可能である可能性があります (この場合、実行時間はペア ( x、y )の関数として計算されます)。関数f ( x ) = 2 ^xにはこの特性があります。

すべての決定問題は、決定問題に関連付けられたセットの特性関数を計算する関数問題に変換できます。この関数が計算可能であれば、関連付けられた決定問題は決定可能です。ただし、この縮小は、計算複雑性で使用される標準的な縮小 (多項式時間多対一縮小と呼ばれることもあります) よりも自由です。たとえば、NP 完全問題とその共 NP 完全 補数の特性関数の複雑性は、基礎となる決定問題がいくつかの一般的な計算モデルでは同等であるとは見なされない場合でもまったく同じです。

各入力に対して正しい答えが 1 つしかない決定問題とは異なり、最適化問題は特定の入力に対する最適な答えを見つけることに関係しています。最適化問題は、巡回セールスマン問題や線形計画法の多くの問題など、多くのアプリケーションで自然に発生します。

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

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

• すべて（複雑さ）
• 計算上の問題
• 決定可能性 (論理) - 式が論理理論の結果であるかどうかを判断する問題。
• 検索の問題
• 数え上げ問題（複雑さ）
• 文章題（数学）

• コゼン、DC (2012)。オートマトンと計算可能性。スプリンガー。ISBN 978-1-4612-1844-9。
• ハートリー、ロジャース・ジュニア（1987年）。再帰関数と実効計算可能性の理論。MIT出版。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。