- 締切済み
NP完全問題、NP困難問題についての質問です。
下記の問題が存在するとされているか、存在しないとされているか、もしくはどちらでもないかを教えてください。 どちらでもないものに対しては、簡単でいいのでなぜどちらでもないとされているのか教えて下さい。 1) 指数時間内で解けないNP完全問題 2) 指数時間内で解けないNP困難問題 3) NP内に存在するNP完全でない問題 よろしくお願いします。
- 2009googoo
- お礼率36% (46/125)
- 数学・算数
- 回答数1
- ありがとう数0
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
回答No.1
4つの問題のクラス, NP/NP完全/NP困難/指数時間の間の関係は理解できていますか?
