P vs. NP
きたまさによると *1 P=NP らしいですし、未来のわたさんによると*2 G○○gle も P=NP であることを示し、多項式時間アルゴリズムを隠し持っているらしいです。 一方で、P/=NP でも実用上は多項式時間と同等となるような底のすごく小さい指数時間アルゴリズムが存在するかもしれないと、わたさんが示唆しています。
ファンタジーの世界はさておき、エイプリルフールの今日捏造論文が熱いですが、P vs. NP は計算機科学において最も偽論文が熱い分野の1つと言えます。 P-versus-NP page のように嘘証明が取り放題のページもあります。また、 Computer Science authors/titles recent submissions に常駐すると月に数本程度 P vs. NP 系の嘘証明が流れてきます。あなたも証明撃墜にチャレンジ！
