巡回セールスマン問題メモ

多項式時間(n,n^2,n^3,nlognなど)で解けるアルゴリズム⇒polynomial-time solvable クラスP

ある問題がクラスPであることを証明⇒多項式時間アルゴリズムを１つでも探せばよい

巡回セールスマン問題：多項式時間アルゴリズムが存在しないことが予想されている（証明できていない）
不可能を証明することはとても難しい！！

巡回セールスマン問題⇒NP完全問題に分類（みんなが難しいといっているので難しい！）

クラスNPについては勉強の必要あり（一読ではよくわかりません）