Loading article…
理論計算機科学において、問題とはアルゴリズムによる解決を求める問題のことである。例えば、因数分解の問題など。
は、既知の整数因数分解アルゴリズムが多数存在するため、解を持つ計算問題です。計算問題は、インスタンスまたはケースの集合と、各インスタンス/ケースに対する（空集合の場合もある）解の集合として考えることができます。問題は、インスタンスを解にマッピングするアルゴリズムが存在するかどうかです。たとえば、因数分解問題では、インスタンスは整数nであり、解はnの非自明な素因数である素数pです。解を持たない計算問題の例として、停止問題があります。計算問題は、理論計算機科学における主要な研究対象の一つです。
アルゴリズムの存在そのものだけでなく、その効率性にも関心を持つことが多い。計算複雑性理論の分野は、与えられた問題を解決するために必要なリソース量（計算複雑性）を決定し、なぜ一部の問題が扱いにくい、あるいは決定不能なのかを説明することで、こうした疑問に答える。解決可能な計算問題は、様々な抽象マシンを用いて計算（解決）するために必要なリソース（例えば、時間、空間/メモリ、エネルギー、回路深度）を広く定義する複雑性クラスに属する。例えば、複雑性クラスには、
インスタンスとソリューションの両方は、バイナリ文字列、つまり {0, 1} *の要素で表されます。[ a ]例えば、自然数は通常、バイナリ符号化を使用してバイナリ文字列として表されます。これは、複雑さが入力表現の長さの関数として表されるため重要です。
決定問題とは、あらゆる事例に対して「はい」か「いいえ」のどちらかの答えしか得られない計算問題のことです。決定問題の一例として、素数判定が挙げられます。
決定問題は通常、答えが「はい」となるすべてのインスタンスの集合として表されます。たとえば、素数判定は無限集合として表すことができます。
探索問題では、答えは任意の文字列になり得ます。例えば、素因数分解は探索問題であり、インスタンスは正の整数（の文字列表現）であり、解は素数の集合（の文字列表現）です。
探索問題は、すべてのインスタンスと解のペアからなる関係として表現され、これを探索関係と呼びます。たとえば、因数分解は、次の関係として表現できます。
これは、 pがnの素因数であるような、すべての数のペア( n、p )から構成されます。
数え上げ問題とは、与えられた探索問題の解の数を求める問題です。例えば、因数分解に関連する数え上げ問題は次のようになります。
計数問題は、{0, 1} *から非負整数への関数fで表すことができます。検索関係Rの場合、 Rに関連付けられた計数問題は関数です。
最適化問題とは、探索問題におけるすべての可能な解の中から「最良の」解を見つけることを求める問題である。その一例として、最大独立集合問題が挙げられる。
最適化問題は、目的関数と制約条件によって表される。
関数問題では、入力ごとに単一の出力（全関数の出力）が期待されますが、その出力は決定問題の出力よりも複雑で、単に「はい」か「いいえ」ではありません。最も有名な例の1つは、巡回セールスマン問題です。
これは組み合わせ最適化におけるNP困難問題であり、オペレーションズリサーチや理論計算機科学において重要である。
計算複雑性理論では、{0, 1} *に含まれる任意の文字列が、対象となる計算問題のインスタンスを表すと暗黙のうちに仮定されるのが一般的です。しかし、{0, 1} *に含まれるすべての文字列が有効なインスタンスを表すとは限らない場合があり、その場合は {0, 1} *の適切な部分集合を「有効なインスタンス」の集合として指定します。このような計算問題は、プロミス問題と呼ばれます。
以下は、（決定）約束問題の一例です。
ここで有効なインスタンスとは、独立集合の最大サイズが5以下または10以上のグラフのことである。
決定約束問題は通常、 {0, 1} *の互いに素な部分集合のペア ( L yes、L no ) として表現されます。有効なインスタンスは、L yes ∪ L noに含まれるものです。L yesとL no は、それぞれ答えがyesとno であるインスタンスを表します。
約束問題は、近似の困難性、特性テスト、対話型証明システムなど、計算複雑性のいくつかの分野で重要な役割を果たしています。