複雑性クラス

この記事は最近勉強し始めたので、これからに期待される内容です。
初手から間違っていることもあります。

コンピューターにできることとできないこと

決定不能問題

この世には、そもそも既存のコンピューターを用いて解けない問題があり、それらは決定不能問題と呼ばれる。

停止性問題(halting problem)
プログラムは与えられたプログラムが有限時間内に停止するか否かを判定できない。

bool isHalting(Function f)
{
  //停止性を解決できる理想の処理
}

void g()
{
  if(isHalting(g))
  {
    while(true){}//無限ループ
  }
}

停止性を判定できるisHaltingなる理想の関数があると仮定する。
isHaltingは入力された関数fが停止するならtrueを返す
isHaltingは入力された関数fが停止しないならfalseを返す
関数g()はisHaltingがtrueなら無限ループに突入し、isHaltingがfalseならisHalting内で無限ループに突入している。
この矛盾により、停止性を判定できるisHaltingなる関数の仮定が誤りである。isHaltingは存在しない。

決定問題

YesかNo、TrueかFalse、0か1などで事の真偽が判定できる問題。
与えられた自然数は素数か、など。
我々がコンピューターに解いてほしいと期待するのはだいたいこの問題に帰着できる。これらの問題はクラスPやNPに属する。

複雑性クラス

コンピューターに解ける問題。解いてほしい問題。すなわち決定問題の中にすら現実的に解けない問題がある。それらはNP完全と呼ばれるクラスに含まれる。ただしNP完全であってもやりようによってはいけたりもするし、$${P\neq NP}$$が証明されていないせいで話が２パターンあり、ややこしい。

クラスP

多項式時間（polynomial time）で解ける決定問題のクラスである。

例えば普通のその辺の配列やリストを最初から最後まで操作する時の多項式は$${n}$$である。ここでnは入力された要素の個数。

//n=arr.length
for(int i = 0; i<arr.length; i++)
{
  //処理
}

上記のループの中でもう一度配列を操作するなら多項式は$${n^2}$$である。

for(int i = 0; i<arr.length; i++)
{
  for(int j = 0; j<arr.length; j++)
  {
    //処理
  }
}

クラスNP

NP (Non-deterministic Polynomial time)は、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。

NP困難のうち、NPに含まれない問題は論外レベルで難しく、
NP困難のうち、NPに含まれる問題はNP完全、相当に難しい。
図はwikipediaを見られよ。

$${P\neq NP}$$の場合
NPとNP困難とがある。NPとNP困難の重複部分がNP完全である。NPにはPが含まれる。

$${P = NP}$$の場合
NPはNP困難に含まれる。NP=NP完全=Pである。

停止性問題はNP困難かつNPでない。
ハミルトン閉路問題はNP困難かつNP。ゆえにNP完全。

ハミルトン閉路問題

グラフの全ての頂点をただ１度だけ通り、最初の頂点に戻ってくる路が得られるかどうかの問題。

ある路がハミルトン閉路か否かを判定するのはたやすい。これをもって『多項式時間で検証できる』とする。

//疑似コード

//pathの始点と終点は同一要素であることが前提
bool isHamilton(List<Vector2D> graph, List<Vector2D> path)
{
  //得られる閉路はgraphの頂点数+1のはず
  if(graph.count+1!=path.count){return false;}
  //閉路でないならfalse
  if(path[0]!=path[path.count-1]){return false;}

  //pathの重複要素を探す、終点は始点と同一であることが前提であるため除外  
  for(int i = 0; i<path.count-1; i++)
  {
    //pathの頂点がグラフに属さない
    if(!graph.contain(path[i])){return false;}

    for(int j = i+1; j<path.count-1; j++)
    {
      if(path[i]==path[j]){return false;}
    }
  }

  //このpathは多分ハミルトン閉路である
  return true;
}

しかし、あるグラフにハミルトン閉路が存在するか否かを判定するのは極めて困難。なぜならば候補となるパスのパターンが多過ぎて組み合わせが爆発するからである。
このように、得られた解が正しいか否かを判定するのは容易でも、その過程でパソコンがしぬような問題は、NP困難かつNPであるところのNP完全に属する。

巡回セールスマン問題

巡回セールスマン問題はNP困難であり、ハミルトン閉路問題のように解の検証すら多項式時間に完了する保証がない。
巡回セールスマン問題は頂点間の経路にコストが掛かり、ハミルトン経路かつコスト最小のパスを求める問題である。コスト最小を判定するには全てのパスと比較しなければならないため、その時点で組み合わせが爆発する。