computation - R\P の問題 (例を探す)

Question

私は計算可能性理論を研究しており、明らかに解決できる問題を探していますが、多項式時間では解決できません。

ありとあらゆる例を考えてみましたが、多項式時間で解けない理由がわかりませんでした..

Answer 1

巡回セールスマン問題。