Lance Fortnow が CACM にサーベイを書いたのがニュースになっていたので読んでみました。
The 1979 book of Garey and Johnson still gives the best overview ...
とか書いてある... おぃおい〜 30年全然進んでないんですか。
Aaronson, S. Is P versus NP formally independent?
Bulletin of the European Association for Theoretical
Computer Science 81 (Oct. 2003).
とか面白そう。これによると決定不能問題ではなさそうらしい。こっちは20ページもあるので、そう簡単には読めないが... でも、あまり根拠はないっぽい。
でも、ill defined な問題である可能性はあると思う。P/NP は Turing Machine に対して定義されるんだけど、テープの長さと時間は決めてあるが、計算するオートマトンの大きさは規定されてないから。
http://www.win.tue.nl/~gwoegi/P-versus-NP.htm
こっちの方が面白いな...
No comments:
Post a Comment