意味
意思決定問題のための形式言語の文脈では、言語は
$$ {L_1\!} $$
多項式時間で言語に還元できる$$ {L_2\!} $$
（注記$$ {L_1 \le_P L_2} $$
)多項式時間で計算可能な関数が存在する場合$$ {f : \left\{0,1\right\}^* \rightarrow \left\{0,1\right\}^*} $$
あらゆるものに対してなど$$ {x \in \left\{0,1\right\}^*} $$
、 $$ {x \in L_1} $$
もし、そしてその場合に限り$$ {f(x) \in L_2} $$
。関数を呼び出します$$ {f\!} $$
リダクション関数、および次の値を計算する多項式アルゴリズム$$ {f\!} $$
はリダクションアルゴリズムと呼ばれます。
意思決定の問題とそれに関連する言語との関係
コーディング
どちらか
$$ {Q\!} $$
決断の問題。この問題のインスタンスは、その定義が純粋に数学的であるという意味で抽象オブジェクトです。ただし、この問題を実装できるようにするには、プログラムが理解できる形式で表現する必要があります。ここでコーディングの概念が登場します。コーディング関数を定義します$$ {c\!} $$
意思決定の問題の$$ {Q\!} $$
の抽象インスタンスのセットに関連する単射的アプリケーションとして$$ {Q\!} $$
の要素$$ {\left\{0,1\right\}^*} $$
。したがって、プログラマーが問題をコード化すると、問題のインスタンスを表す変数が (静的言語の場合はコンパイラーによって、動的言語の場合はインタープリターによって) バイナリ言語に変換されます。したがって、コーディングは抽象的な問題から具体的な問題に移行する方法です。実際、抽象的な意思決定問題のインスタンスに対する解決策があれば、 $$ {i \in I} $$
東$$ {Q(i) \in \left\{0,1\right\}} $$
次に、具体的な問題インスタンスの解決策$$ {c(i) \in \left\{0,1\right\}^*} $$
もです$$ {Q(i)\!} $$
。ただし、少し問題が発生します。 $$ {\left\{0,1\right\}^*} $$
問題のどのインスタンスとも一致しません (つまり、前件がありません)。便宜上、このタイプの文字列にはイメージ 0 があると仮定します。
意思決定問題とそれを解決するアルゴリズムの関係
- アルゴリズム$$ {A\!} $$文字列を受け入れる$$ {x \in \left\{0,1\right\}^*} $$入力が与えられた場合$$ {x\!} $$、アルゴリズムの出力$$ {A(x) = 1\!} $$
- アルゴリズム$$ {A\!} $$文字列を拒否します$$ {x\!} $$もし$$ {A(x) = 0\!} $$。
受け入れられる言語
- アルゴリズムが受け入れる言語$$ {A\!} $$アルゴリズムによって受け入れられる文字列のセットです。つまり、$$ {L = \left\{ x \in \left\{0, 1\right\}^* : A(x) = 1\right\}} $$。
明確な言語
- 言語$$ {L\!} $$アルゴリズムによって決定される$$ {A\!} $$に属さないバイナリ文字列がある場合$$ {L\!} $$によって拒否されます$$ {A\!} $$。
複雑さのクラスと言語
複雑さのクラスを、特定の文字列かどうかを決定するアルゴリズムの複雑さの尺度によってメンバーシップが決定される言語のセットとして非公式に定義できます。
$$ {x\!} $$
言語に属する$$ {L\!} $$
。したがって、複雑さのクラスは$$ {P\!} $$
上の言語のセットとして定義できます。 $$ {\left\{0,1\right\}^*} $$
これらは多項式時間アルゴリズムによって決定されます。ユーティリティ
多項式時間の短縮の概念は、問題の分類を可能にするために複雑性理論の枠組み内で使用されます。これにより、ある問題が別の問題と少なくとも同じくらい難しいことを、多項式時間で形式的に示すことが可能になります。
$$ {L_1 \le_P L_2} $$
それで$$ {L_1\!} $$
よりも難しくない$$ {L_2\!} $$
、または、より理論的には次のように言えます。 $$ {L_1\!} $$
そして$$ {L_2\!} $$
同じ複雑さクラスを持ちます。割引例
- サブセット合計までカバー
- クリックして3 土曜日まで
- 土～3土
- 飽和までのサブセット合計
- 3-Satからクリークへ
- 3-sat から頂点カバーまで