computation - R\P 中的问题（寻找示例）

Question

我正在研究可计算性理论，我正在寻找一个显然可以解决但不能在多项式时间内解决的问题。

我试着想各种各样的例子，但不清楚为什么它们不能在多项式时间内解决..

Answer 1

旅行商问题。