第4章 NP完全
==
易しい問題：問題（入力）の規模nの多項式で表せる実行時間で求解するアルゴリズムが存在する問題。

難しい問題：上記のようなアルゴリズムが知られていない問題。すなわち、今まで知られている最良のアルゴリズムをもってしても計算量がO(n!),o(2^n)などとなってしまう問題。
<br/>

例1(オイラー閉路問題,一筆書き問題)

グラフG(節点Vと枝Eからなる)が与えられたとき,Gのある節点v_0から出発して,すべての枝をちょうど1回ずつ通過して元のv_0に戻るような経路は存在するか？
定理：オイラー閉路が存在するための必要十分条件は
(1)各節点から任意の節点への経路が存在する連結性),かつ
(2)すべての節点において次数(枝の数)が偶数である.

オイラー閉路の構成
適当に閉路を構成してゆく,
2つの閉路が交差したならば,1つの閉路に再構成できることは明らか。オイラー閉路問題は易しい問題である。

<br/>
例2(ハミルトン閉路問題,巡回セールスマン問題)：
グラフGが与えられたとき、Gのある節点v_0から出発してすべての節点をちょうど1回ずつ通過してもとのv_0に戻るような経路は存在するか?


ハミルトン閉路は難しい問題である。

### 非決定性モデル
非決定性モデル(チューリング機械の拡張：非決定性チューリング機械)では前述のチューリング機械の命令の他に

choice(S)

という基本操作が許される。choiceは神託もしくは乱数などによって適当な値(状態)をひとつ選ぶ、内容不明の命令である。
これはチューリング機械において、ある状態である記号を読んだときの動作が一通りとは限らず,複数個ありうるとするものである。
形式的には、動作表が多価関数でも良いということである。次の動作が複数個ある場合、そのうちどれを選ぶかはわざと決めないでおく。