>82
TMが停止しない問題はまた別の話ですよ。
P/NPは「DTM/NTMで多項式時間で受理可能な問題」という強烈な制限がありますので、
基本的には停止しない問題になります。
＃>88の「NP困難問題」と言ってしまうとちょっと行き過ぎですね。NP困難はどんな難しい問題も含むので、
＃停止問題とかもNP困難になります。この場合「NP完全」というのが多分正解

魅力として最も実際的な話は、>83の言う通り暗号関連の部分ですね。
P!=NPなら、現在のコンピュータで
「パスワードがあると簡単だけど無いと解くのが難しい問題」
「元のソースから簡単にデータを生み出せるけど、生み出したデータからソースを作るのは難しいハッシュ関数」
とかの存在が保証されます。
実際、P完全とNP完全の大きな違いがそこですし。