Monday, 12 October 2009

P!=NP

P!=NP は、何回か触れてます。P=NP 論者です。ってのも書いたはず。

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

こっちの方が面白いな...

Post a Comment