チューリングマシンと計算複雑性：Pクラス・NPクラスの定義と意味
はじめに：計算複雑性理論の世界へようこそ
チューリングマシンは、計算の基本的なモデルとして計算可能性理論において中心的な役割を果たします。しかし、ある問題が「計算可能であるか」という問いだけでなく、「どれだけ効率的に計算できるか」という問いもまた、計算機科学において極めて重要です。この効率性に関する問いを扱うのが、計算複雑性理論です。
本記事では、計算複雑性理論における最も基本的なクラスであるPクラスとNPクラスに焦点を当て、これらのクラスがチューリングマシンを用いてどのように定義されるかを解説します。抽象的な理論が、チューリングマシンの具体的なモデルとどのように結びつくのかを理解することで、計算の限界や効率性に関する洞察を深めることができるでしょう。
チューリングマシンにおける「効率性」の定義：計算時間と領域計算量
計算複雑性理論では、アルゴリズムの効率性を測る尺度として主に計算時間と領域計算量（メモリ使用量）を用います。チューリングマシンの文脈では、これらは以下のように定義されます。
- 計算時間: 入力テープに書かれた文字列の長さ $n$ に対して、チューリングマシンが停止するまでに実行するステップ数の上限です。この上限を $T(n)$ と表現し、$O(T(n))$ のようにオーダー記法で記述することが一般的です。
- 領域計算量: 入力テープの長さ $n$ に対して、チューリングマシンが計算中にテープ上で使用するセルの数の上限です。これを $S(n)$ と表現し、$O(S(n))$ のように記述します。
本記事で扱うPクラスやNPクラスは、主に「計算時間」に関するクラスであり、特に「多項式時間」で解ける問題に注目します。多項式時間とは、計算時間が入力サイズの多項式 $O(n^k)$ （$k$ は定数）で抑えられる計算時間のことです。入力サイズに対して計算時間が指数関数的に増加する問題と比較して、多項式時間で解ける問題は「効率的に解ける」と見なされることが多いです。
決定問題と計算複雑性クラス
計算複雑性理論で主に扱われるのは「決定問題」と呼ばれる種類Tの問題です。決定問題とは、入力に対して「はい」か「いいえ」のいずれかで答えられる問題です。例えば、「与えられたグラフにハミルトン閉路は存在するか？」や「与えられた整数 N は素数か？」といった問題が決定問題にあたります。
計算複雑性クラスは、特定のリソース（計算時間や領域計算量）の制約内で解ける決定問題の集合として定義されます。ここで、中心となるのがPクラスとNPクラスです。
Pクラス：効率的に「解ける」問題のクラス
Pクラスは、決定性チューリングマシン (Deterministic Turing Machine, DTM) によって多項式時間で解くことができる決定問題のクラスです。
決定性チューリングマシンとは、現在の状態とヘッドが読み取った記号によって、次に取るべき動作（書き込む記号、ヘッドの移動方向、次の状態）が一意に決まるチューリングマシンのことです。これまでシミュレーターで扱ってきたチューリングマシンは、この決定性チューリングマシンに該当します。
ある決定問題がPクラスに属するということは、その問題を解くためのアルゴリズムが存在し、そのアルゴリズムを決定性チューリングマシン上で実行した際に、計算時間が入力サイズの多項式で抑えられることを意味します。これは、実用的な計算機（多くの場合は決定的な動作をします）で効率的に解ける問題であることの理論的な根拠となります。
例えば、「与えられた配列に特定の要素が含まれているか？」という検索問題や、「与えられた2つの整数を掛け合わせた結果が、与えられた第三の整数と等しいか？」という問題などは、多項式時間で解くことができるため、Pクラスに属します。
NPクラス：効率的に「検証できる」問題のクラス
NPクラスは、非決定性チューリングマシン (Non-deterministic Turing Machine, NTM) によって多項式時間で解くことができる決定問題のクラスです。
非決定性チューリングマシンとは、現在の状態と読み取った記号に対し、次に取るべき動作が複数存在する可能性があるチューリングマシンのことです。非決定性チューリングマシンは、計算の各ステップで複数の可能な遷移の中から「正しい」遷移（受理状態に至る遷移）を「推測」して実行できる、という抽象的なモデルです。非決定性チューリングマシンがある入力を「受理」するのは、可能な計算経路のうち、少なくとも一つが受理状態に到達する場合です。
NPクラスの定義は、非決定性チューリングマシンを用いる以外に、もう一つの重要な視点があります。それは、「YESインスタンスに対する『証明』が与えられたとき、その証明が正しいかどうかを決定性チューリングマシンで多項式時間で検証できる」決定問題のクラスである、という定義です。この「検証可能」という視点の方が、NPクラスを直感的に理解しやすい場合があります。
例えば、「与えられたグラフにハミルトン閉路は存在するか？」という問題（ハミルトン閉路問題）を考えます。グラフ自体は大きいかもしれませんが、もし「はい、存在します」という答えに対する「証明」として、実際にハミルトン閉路を構成する頂点の順序が与えられたとします。決定性チューリングマシンは、与えられたグラフとこの頂点の順序を入力として受け取り、その順序がグラフ内の有効な経路であり、全ての頂点を一度ずつ通って始点に戻るかを多項式時間でチェックすることができます。したがって、ハミルトン閉路問題はNPクラスに属します。
NPクラスに属する有名な問題には、充足可能性問題 (SAT)、巡回セールスマン問題 (TSP) の決定問題版、ナップサック問題などがあります。これらの問題に対して「YES」であることの「証明」（SATなら変数の割り当て、TSPなら巡回経路など）が与えられれば、その証明が正しいかどうかを効率的に（多項式時間で）確認できるのです。
PクラスとNPクラスの関係：P = NP 問題
Pクラスに属する問題は、決定性チューリングマシンで多項式時間で解けます。決定性チューリングマシンは、非決定性チューリングマシンの特別な場合（常に遷移が一意に決まる場合）と見なせるため、Pクラスに属する問題は、非決定性チューリングマシンでも多項式時間で解けることになります。したがって、PクラスはNPクラスに含まれます（P ⊆ NP）。
計算機科学における最も有名な未解決問題の一つが、「P = NP であるか、P ≠ NP であるか」という問題です。
- もし P = NP であれば、それはNPクラスに属する全ての問題（例えば、ハミルトン閉路問題やSATなど、現在効率的な解法が見つかっていない多くの問題）に対して、決定性チューリングマシンによる多項式時間アルゴリズムが存在することを意味します。これは、多くの困難な問題が一気に「効率的に解ける」ようになる、という驚くべき結論を導きます。
- もし P ≠ NP であれば、NPクラスに属する問題の中には、決定性チューリングマシンでは決して多項式時間では解けない問題（本質的に難しい問題）が存在することを意味します。多くの研究者の予想はこちらの P ≠ NP ですが、厳密な証明はまだ見つかっていません。
このP = NP問題の解決は、計算機科学だけでなく、数学、暗号、人工知能など、幅広い分野に壊滅的、あるいは革命的な影響を与えるとされています。クレイ数学研究所によってミレニアム懸賞問題の一つにも指定されており、解決者には100万ドルの賞金がかけられています。
シミュレーターとの関連性
本記事で紹介したPクラスとNPクラスは、チューリングマシンの抽象的な定義に基づいています。お手元のチューリングマシンシミュレーターを使って特定のアルゴリズム（例えば文字列コピーや簡単な算術演算など）を実装し、その動作ステップ数を数えてみてください。入力サイズ $n$ とステップ数の関係を観察することで、「計算時間」という概念や、それがどのようにチューリングマシン上で計測されるのかをより具体的にイメージできるはずです。
また、非決定性チューリングマシンの概念は、シミュレーターが決定性マシンであることを踏まえると、そのシミュレーションの難しさを浮き彫りにします。一般に、非決定性チューリングマシンの計算は、決定性チューリングマシン上では指数関数的な時間が必要になることが知られています（可能な計算経路を全て探索する必要があるため）。これが、NPクラスの問題がPクラスに含まれるとは考えにくい一因でもあります。
まとめ
計算複雑性理論は、問題の計算可能性だけでなく、その効率性に着目する分野です。チューリングマシンという計算モデルを用いることで、効率的に「解ける」問題のクラスであるPクラスと、効率的に「検証できる」問題のクラスであるNPクラスを厳密に定義できることをご紹介しました。
P ⊆ NP であることは証明されていますが、P = NP か P ≠ NP かは未だ数学上の大きな謎です。この問題は、理論計算機科学の根幹に関わるだけでなく、私たちが日常的に直面する多くの問題の「難しさ」の性質を理解する上でも極めて重要な意味を持っています。
本記事が、チューリングマシンの理論が計算の効率性という新たな視点とどのように結びつくのかを理解する一助となれば幸いです。引き続きシミュレーターを活用し、チューリングマシンの奥深い世界を探求してみてください。