1 定義
完全問題とは、ある複雑性クラスに属する問題のうち、そのクラスの中で代表的に難しいとみなされる問題である。対象クラスの任意の問題が、適切な変換を通じてその問題へ帰着できるとき、当該問題はそのクラスに対して完全であるという。したがって、完全問題はクラス全体の性質を端的に反映する指標として用いられる。
完全性は、単に計算量が大きいことを意味するだけではない。クラス内の他の問題をすべて受け止められる普遍性を持つ点に特徴がある。そのため、完全問題の存在は、複雑性クラスの構造や境界を理解するための重要な手がかりになる。
1.1 複雑性クラス
複雑性クラスは、計算に必要な時間、空間、乱択、非決定性、あるいは出力の形式など、何らかの資源制約に基づいて問題を分類した集合である。たとえば、P、NP、PSPACE などは代表的な決定問題のクラスとして知られている。
この分類は、同じ「解ける問題」であっても、どの程度の資源を要するかによって性質が異なることを表す。完全問題は、そうしたクラスの内部構造を一つの問題に集約して示す役割を果たす。
1.2 還元
還元とは、ある問題を別の問題へ変換し、後者を解くことで前者も解けるようにする手法である。複雑性理論では、還元によって問題間の難しさを比較する。
完全性の議論では、還元は中心的な道具である。ある問題が他のすべての問題を受け入れられる形で変換可能なら、その問題はクラスの代表的な難問と見なされる。
1.2.1 多項式時間還元
多項式時間還元は、変換に要する計算時間が入力サイズの多項式で抑えられる還元である。計算機科学では、実用的な効率性の基準として広く用いられている。
この還元は、NP 完全性などの議論で特に重要である。変換自体が現実的な計算量の範囲にあるため、理論上の難しさを比較する際の標準的な枠組みとなっている。
1.2.2 対数空間還元
対数空間還元は、変換の際に使用できる補助記憶が入力サイズの対数程度に制限される還元である。時間ではなく空間資源を強く抑えた変換であり、細かなクラス比較に用いられる。
この種類の還元は、P 完全性や PSPACE に関する研究で現れることがある。より厳しい制約のもとでの変換であるため、問題の本質的な構造を見分ける際に有効である。
1.3 完全性
完全性とは、ある問題が特定の複雑性クラスに属し、かつそのクラスの任意の問題がそれに還元できる性質である。要するに、所属性と困難性の両方を満たすことが条件になる。
完全問題は、そのクラスの中でも最も扱いにくい候補として機能する。ひとたび完全性が示されれば、その問題を解く効率的な方法は、クラス内の全問題に対する効率的な方法を与えることになる。
2 代表的な完全問題
完全問題には、決定問題、計数問題、最適化問題など、対象の問題形式に応じたさまざまな代表例がある。これらは理論上の基準点として用いられ、他の問題の難度を比較する際の目印になる。
特に、NP 完全問題は計算複雑性理論の中心的話題の一つである。一方で、計数や最適化の分野にも、それぞれ独自の完全問題が存在する。
2.1 決定問題の完全問題
決定問題の完全問題は、答えが「はい」か「いいえ」で与えられる問題の中で、あるクラス全体を代表するものを指す。NP 完全問題はその典型であり、理論計算機科学で最も広く知られている。
これらの問題は、組合せ構造や制約充足の形で現れることが多い。見た目は異なっても、還元を通じて互いに結び付けられる点が重要である。
2.1.1 充足可能性問題
充足可能性問題は、論理式に対して、ある真偽値の割り当てで全体を真にできるかを問う問題である。とりわけ命題論理の充足可能性問題は、NP 完全性の古典的な例として知られる。
この問題は、制約を満たす組合せの存在を問う構造を持つため、多くの別問題の出発点になる。アルゴリズム研究では、SAT ソルバとして発展し、実際の検証や設計支援にも応用されている。
2.1.2 頂点被覆問題
頂点被覆問題は、与えられたグラフの各辺を少なくとも一方の端点で覆う頂点集合が、所定の大きさ以下に存在するかを判定する問題である。これは典型的な NP 完全問題の一つである。
グラフ理論に自然に現れるため、構造的な理解がしやすい。ほかの組合せ最適化問題との関連も深く、還元の教材として頻繁に取り上げられる。
2.2 計数問題の完全問題
計数問題は、解の存在だけでなく、その総数を求めることを目的とする。これらは決定問題よりも情報量が多く、しばしばより繊細な分類が必要になる。
完全問題としての計数問題は、解の個数を扱うクラス、たとえば #P に関する研究で中心的な役割を担う。存在判定よりも一段複雑な性質を持つことが多い。
2.2.1 充足割り当て数え上げ問題
充足割り当て数え上げ問題は、論理式を真にする真偽値割り当ての総数を求める問題である。これは #P 完全の代表例とされる。
この問題は、解の有無ではなく解空間の規模を明らかにする点で特徴的である。確率的推定や組合せ列挙とも関係し、理論面と応用面の双方で重要性が高い。
2.2.2 経路数え上げ問題
経路数え上げ問題は、グラフやネットワークの中で条件を満たす経路の総数を求める課題である。問題設定によっては、#P 完全性を示す典型例になる。
この種の問題は、通信網、輸送網、確率過程の解析などと結び付く。決定問題よりも解の分布に関する情報を含むため、計算の難しさが際立つ。
2.3 最適化問題の完全問題
最適化問題の完全問題は、条件を満たす解の中で、目的関数を最大化または最小化するものを指す。厳密には、決定問題の完全性とは別の枠組みで論じられることが多い。
これらは実務上の関心も高く、輸送計画、設計、資源配分などに直接現れる。完全性は、近似の困難さや探索の難度を理解する際の基礎となる。
2.3.1 巡回セールスマン問題
巡回セールスマン問題は、与えられた都市を一度ずつ訪れて出発点に戻る最短経路を求める問題である。最適化版は古典的な難問として広く知られている。
この問題は、組合せ爆発の代表例として扱われる。決定版も NP 完全であり、最適化版は実用アルゴリズムと理論解析の両面で重要である。
2.3.2 最大クリーク問題
最大クリーク問題は、グラフ中の完全グラフ部分のうち、頂点数が最大のものを見つける課題である。これも代表的な困難問題として知られる。
局所的な隣接関係から全体構造を探る必要があるため、探索空間が急速に増大する。グラフ解析や近似理論において、基準的な難問として位置付けられている。
3 完全性の証明
完全性を示すには、対象問題がクラスに属することと、クラス内の任意の問題から帰着されることの両方を証明する必要がある。前者は所属性、後者は困難性の証明に対応する。
証明の技法は問題の種類やクラスによって異なるが、基本的な考え方は共通している。既知の完全問題を足がかりにする方法が特に一般的である。
3.1 困難性の示し方
困難性の示し方は、対象問題が少なくともクラス内の任意の問題と同程度に難しいことを明らかにする作業である。多くの場合、すでに完全性が分かっている問題からの帰着を構成する。
この段階では、元の問題の構造を保ちながら、対象問題の入力へ適切に写像することが求められる。変換の正しさと計算量の制約の両方が重要である。
3.1.1 既知の完全問題からの還元
既知の完全問題からの還元は、古典的で信頼性の高い証明法である。たとえば SAT から別の問題へ変換できれば、その問題の困難性を示しやすい。
この方法は、複雑な問題を段階的に比較するうえで有効である。還元の鎖を作ることで、複数の問題の難しさの関係を体系的に整理できる。
3.1.2 問題の構成法
問題の構成法では、対象問題に対して、入力を工夫して完全性を直接示す。論理式、グラフ、遷移規則などを組み立て、解の対応関係を精密に設計する。
この手法は、単なる写像以上に、問題の内部構造を理解していることが求められる。証明としてはやや技巧的だが、新しい完全問題の発見には欠かせない。
3.2 所属性の示し方
所属性の示し方は、対象問題が確かにその複雑性クラスの定義内に収まることを確認する作業である。困難性だけでは完全性は成立しないため、必須の部分である。
実際には、与えられた解候補を効率よく検証できるか、あるいは必要な資源制約内で計算できるかを示す。問題形式に応じて、証明の方法は変わる。
3.2.1 クラス内に含まれることの証明
クラス内に含まれることの証明は、問題を解く手続きがそのクラスの資源制約を満たすことを示す。たとえば、NP であれば非決定的多項式時間、P であれば決定的多項式時間であることを確認する。
この証明が成立して初めて、対象問題は完全問題候補となる。困難性との組み合わせにより、初めて完全性が確定する。
3.2.2 検証可能性
検証可能性は、ある解候補が正しいかどうかを効率的に確かめられる性質である。NP の定義では、証明書を多項式時間で検証できることが中心となる。
検証の容易さは、探索の難しさと対照的である。解を見つけることが難しくても、見つかった解を確かめるのは比較的簡単、という構図がしばしば現れる。
4 主要な複雑性クラスとの関係
完全問題は、さまざまな複雑性クラスの性質を映し出す。どのクラスに完全問題が存在するかは、そのクラスの豊かさや閉性と深く関係する。
また、完全問題の有無は、クラス間の相対的な違いを理解する助けにもなる。理論的には、階層構造や包含関係の研究に直結する話題である。
4.1 計算量階層
計算量階層は、資源制約に応じて問題を細かく層別化した枠組みである。上位の層に進むほど、問題の表現力や難度が増すと考えられる。
完全問題は、各層の内部構造を代表する役割を持つことがある。階層の崩壊や分離に関する議論でも、完全性は重要な指標になる。
4.2 決定性と非決定性
決定性と非決定性の差は、計算の進め方に関する基本的な区別である。決定的計算では手順が一意に進むのに対し、非決定的計算では複数の選択肢を同時に考える。
完全問題は、この違いを可視化するのに役立つ。たとえば NP 完全問題は、非決定性の力を要するが、決定的には一般に解法が知られていない問題群の中心に位置する。
4.3 計数可能性
計数可能性は、解の存在だけでなく、解の個数や構造的な分布を扱う性質である。計数クラスでは、出力が数値として表されるため、決定問題よりも情報が豊かである。
計数問題の完全性は、組合せ構造の複雑さを示す強い証拠になる。数え上げが難しいことは、単なる判定よりも解析対象が精密であることを意味する。
4.4 最適化可能性
最適化可能性は、与えられた条件下で最良の解を探せるかどうかに関わる。完全問題は、最適値の探索が本質的に困難であることを示す標識となる。
最適化の完全性は、近似のしやすさにも影響する。厳密解が難しい場合、どこまで効率的に近い解を求められるかが次の焦点になる。
5 研究上の意義
完全問題の研究は、単なる分類作業ではない。問題間の関係を整理し、どの難しさが根本的で、どの難しさが表面的かを見分けるための基盤を与える。
さらに、完全問題は理論と応用の橋渡しとして機能する。抽象的な複雑性概念が、実際のアルゴリズム設計や計算実験の指針につながる。
5.1 理論計算機科学への影響
理論計算機科学では、完全問題が多くの重要な境界を定めてきた。クラス分離、帰着の技法、階層の理解など、基礎理論の発展に広く関わっている。
完全性の概念があることで、異なる問題を共通の尺度で比較できる。これにより、個別の問題研究が全体像の中に位置付けられる。
5.2 アルゴリズム設計への応用
アルゴリズム設計では、完全問題は「一般には難しい」という判断材料になる。これにより、厳密解を狙うのか、特殊ケースを絞るのか、近似へ切り替えるのかといった方針が立てやすくなる。
また、完全問題の構造を理解することは、新しい手法の発見にもつながる。実装上の工夫や分枝限定法、ヒューリスティックの設計にも影響を与える。
5.3 完全性の限界
完全性は強力な概念だが、万能ではない。すべてのクラスに自然な完全問題があるとは限らず、また完全であっても実際の入力分布では扱いやすい場合がある。
加えて、還元の選び方によって完全性の意味合いは変わる。どの資源制約を許すかによって、同じ問題でも評価が異なる点が限界として意識される。
6 関連する概念
完全問題の周辺には、難しさを比較するための関連概念が多数ある。とくに困難問題、近似困難性、完全性の崩壊条件は、完全性の理解を補完する。
これらの概念は、問題の「解けなさ」を多面的に捉えるために用いられる。完全性だけでなく、解法可能性の境界を探る際にも有用である。
6.1 困難問題
困難問題は、ある基準に照らして解くことが難しいと考えられる問題である。ただし、完全問題ほど強い意味での普遍性は要求されない。
完全問題は困難問題の一種とみなせるが、両者は同義ではない。困難であることに加え、クラス全体を代表する構造を持つ点が完全性の特徴である。
6.2 近似困難性
近似困難性は、最適解そのものだけでなく、十分に良い近似解を得ることすら難しい性質を指す。最適化問題の研究で重要な観点である。
完全問題の周辺では、厳密解の困難さから近似の限界へ議論が広がる。近似可能性の程度は、問題の実用性を判断する上でも大きな意味を持つ。
6.3 完全性の崩壊条件
完全性の崩壊条件とは、仮定されたクラス構造や還元概念が変わることで、完全性の意味が弱まる、あるいは失われる状況を指す。たとえば、クラス間の包含関係が予想と異なる場合、完全問題の位置付けも変化しうる。
この概念は、理論の頑健さを点検するために役立つ。完全性がどこまで普遍的で、どこからが定義依存なのかを見極めるうえで重要である。