コメントで書こうとすると長文になってしまってどうしようもなくなったのでトラックバック.

向こうのダウト=俺です.
DESIGN IT! w/LOVE - ブロゴスフィアで起こる「批判」の応酬を鎮めようとすればNP完全問題にぶつかるかもしれない
本題とは全然関係ない話なんですが, 不正確だなぁと思ったのでコメントしました. ごめんなさい. 以下ツッコミです.

では、非決定論的にというのは一体なにか? それを考えるには原理的にすべての計算が可能であるチューリングマシンが決定論的チューリングマシーンであることを思い出していただくとよい。
ようするに、非決定論的に多項式時間で解くことのできるNP完全問題は、非決定論的コンピュータという仮想機械があったとしたら解くことのできる問題というわけだ。しかし、残念ながらすべてのコンピュータはチューリングマシン同様に決定論的なので、指数関数的に増加する時間をかけることなく、NP完全問題を解くことはできないのだ。

という書き方だと, 「決定性チューリングマシンNP完全問題を解くのに必ず指数時間掛かる」になってしまい, 「多項式時間決定性チューリングマシンではNP完全問題が解けない」, 即ち, P!=NPになります. 正確を期すなら,「今のところ, 多項式時間決定性チューリングマシンでは, NP完全問題が解けないと思われている」 or 「決定性チューリングマシンNP完全問題を解くのに指数時間掛かると思われている」と書くべきかと.

あと今気付きましたが,

  1. 数センチ四方のコンピュータチップや数キロに広がる通信ネットワークの中で、いかにして最も効率的に配線するか
  2. 飛行機の飛行計画をいかに効率的に組むか
  3. 生産ライン上の一連の作業をいかに効率的に配置するか
  4. ソフトウェアの設計。何百万というプログラム・コードの中には、必ず矛盾点があるはず。iTunesで音楽を聴いているときにワープロの上でDeleteキーを押すと、ちょうどそれと同時にEudoraでメールチェックをしていたときに限ってシステムが落ちるかもしれない
  5. 社会における基本ソフトウェアは、個人の行動を制限する法体系だ。複雑に絡み合った法体系は、何百年以上にもわたって肥大化し続けてきた。矛盾や不一致は、プログラムのバグと同じで避けようがない。裁判や国会審議といった絶え間ないベータ・テストによって多くの条項は削除されてきたが、その分新しい条項が次々と導入されている

都合上マークアップをolに変更.
4のバグフィックスはプログラムの停止問題とも絡む可能性があるので, NP完全性より難しいんじゃないでしょうか?