多項式階層

多項式階層

多項式階層（Polynomial hierarchy）は、計算量理論における重要な概念であり、P、NP、co-NPといった問題のクラスを一般化した階層です。この階層は、神託機械を利用することによって定義され、様々なクラスにおける計算問題の解決可能性を探求します。

定義と基本概念

多項式階層は、神託機械によって次のように定義されます。この階層における各クラスは、多項式時間内で解決可能な問題の集合を示しています。具体的には、次のように記述できます：

• - P: 多項式時間内で解決可能な決定問題の集合。
• - NP: 非決定性チューリングマシンを使用し、与えられたパラメータに基づいて解を検証可能な問題の集合。これは、決定問題を解決する際に短い証明が存在する場合、容易に解決可能な問題を含みます。
• - co-NP: NPの補集合であり、全ての証明が無効であるときに短い証明を持つ問題の集合。

これらのクラス間には様々な関係があり、特に P は NP および co-NP よりも小さいとされています。

クラスの階層間の関係

多項式階層は再帰的に定義可能です。以下の関係が成り立ちます：

• - /4 ext{NP} = /4 ext{P}
• - /4 ext{coNP} = /4 ext{Π}

このように、階層内の各クラスはその下位クラスを包含しています。重要な点は、真の包含関係が成り立つかどうかは未解決の問題であり、一般にこれが真であると考えられています。

決定問題とその例

多項式階層内に存在する具体的な問題の例として、「回路最小化」問題があります。この問題は、ある論理関数を最大 k 個のゲートで表すための最小回路が存在するかどうかを判断します。この判断を多項式時間で行える決定問題であり、形式的には次のように表現されています：

• - あるブール関数 f を計算する回路 A に対して、同じ関数 f を最大 k 個の論理ゲートで計算できる回路 B が存在するかどうか。

この問題は、形式的に L という言語で表現され、与えられた入力が L に属するかを判定することで解決されます。

多項式階層の重要性

多項式階層は、計算問題の複雑性を理解する上での基本的な枠組みを提供します。この階層は、NP完全性やPSPACE完全性と密接に関連しており、計算可能性の限界や特定の問題が容易または難しいかを示す指標として機能します。特に、PSPACEとの関係は興味深いものであり、PH が PSPACE に含まれるとされる一方、それらの等しいことが証明されていない点は、理論的な課題として残っています。

計算量理論における多項式階層は、問題解決に向けたアプローチを多様化し、計算の限界を深く洞察する手助けをしています。今後の研究により、その体系や性質がますます明らかになることが期待されます。

もう一度検索