多項式時間変換

多項式時間変換とは

多項式時間変換、または多項式時間還元は計算量理論における重要な概念です。別名、多項式時間帰着とも呼ばれ、ある問題 A から別の問題 B への変換が多項式時間で行える場合に使われます。この変換の結果、問題 A と問題 B の難易度を比較することができます。

定義と種類

多項式時間変換は、ある問題 A のすべての入力を、別の問題 B の入力に変換し、その変換が決定性チューリングマシンによって多項式時間で行えることを指します。これにより、A は B に多項式時間変換可能とされ、記号で表すと A ≤ p B となります。このとき特に注意が必要なのは、変換が問題 A の入力内容に依存しない点です。つまり、A に存在する全ての入力が B に変換可能でなければなりません。

また、多項式時間変換にはいくつかのバリエーションがあります。例えば、Karp 還元と呼ばれる多対一還元や、Cook 還元と呼ばれるチューリング還元があります。それぞれの還元方式は、問題の解法において異なる強さを持っています。

難しさの測定

計算量理論において多項式時間変換は、問題の「難しさ」を測定する手段として効果的です。もし問題 A が問題 B に多項式時間還元可能であるなら、B の解決法があればそれを利用して A も解決できることになります。つまり、問題 B は A よりも同等かそれ以上に難しいという結論が得られます。逆に、A ≤ p B かつ B ≤ p A であった場合、A と B は多項式時間同値であると言い、記号で A ≡ p B と表します。この場合、A と B は同じ難しさを持ちます。

重要性と限界

多項式時間還元は、問題同士の関係を理解するために非常に重要です。その理由は、特に計算上重要なクラスに属する問題を相互に変換できるため、これにより問題の難易度を相対的に評価できます。具体的には、NP完全問題やPSPACE完全問題などのクラスには、多項式時間還元の概念が頻繁に用いられています。

しかし、多項式時間還元が必ずしも全ての問題に適用できるわけではありません。なぜなら、クラス P の中に存在する問題は、P 内のほとんど全ての問題に多項式時間還元できるからです。このため、クラス P 内の問題を扱う際には、対数領域還元などの他の手法が用いられることがあります。

還元の強さと弱さ

多項式時間還元には、チューリング還元と多対一還元の2つの主要な種類がありますが、一般的にチューリング還元の方が強力です。例えば、co-NPに属する問題は任意のNP完全問題に対してCook還元が可能ですが、同じ問題をKarp還元することはできない場合もあります。

このように、還元の種類によって問題の解決手法やその難易度の判断に大きな違いが出てくるのです。具体的には、Karp還元が可能であれば、元の問題がNPに属すると言い切ることができるため、Karp還元の方が問題の精度が高いとされています。

NP完全の例

NP完全である問題は、他のNPに属する問題に多項式時間変換可能であることが証明されています。スティーブン・クックによって、充足可能性問題がNP完全であることが示された後、他の問題も同様にその性質が確認されています。NP完全問題は、最も難易度が高いNP内の問題として位置づけられています。これにより、問題 A が NP完全であれば、他に同じかそれより難しい問題が存在しないことが示され、問題 B も NP完全であるとされます。

このようにして、計算量理論における多項式時間変換は、問題間の複雑性の理解や比較において不可欠な役割を果たします。

もう一度検索