２．ハミルトン検定法

■ハミルトン閉路問題の解を多項式時間内に求めることが，ハミルトン検定法の目標である．与えられたグラフがハミルトンタイを持っている場合には，そのグラフのハミルトンタイの一つの実例を示すことによってこの問題の解答とすることができる．そのグラフがハミルトンタイを持っていない場合には，それを事実として示すことができなくてはならない．

■これはつまりすべての場合を調べ尽くす必要があるということを意味している．組み合わせ問題の場合の個数が問題のサイズＮの階乗のオーダーになってしまうことは避けられない．これが通常，組み合わせ論的爆発と呼ばれる現象である．組み合わせ問題を線形アルゴリズムによって解くことは，ほとんど「海の水を呑み干せ」と言っているに等しい．与えられた「ひしゃく」を使って，海の水を制限時間内に汲み出すなどということが一体可能であろうか？