NP困難問題は必ず指数時間で解けますか？

質問

宿題で大変困っています。もしよろしければ教えて下さい。

NP困難問題で指数時間で解けない問題は存在するのでしょうか?

よろしくお願いします。

回答No.1

Rice-Etude · ベストアンサー

決定不能な問題なら、どれだけ時間をかけても解けないですよね。
「決定不能 問題」で検索してみてください。