OpenAI、計算機科学の定説「指数時間仮説」を覆す
A.I. Just Blew Up a Key Tenet of Computer Science

「解くのは難しく、答え合わせは簡単」——Sudokuの例で語られるこの直感は、P vs. NP問題や1998年に提唱された指数時間仮説(E.T.H.)の土台だった。OpenAIは10月26日、最新のAI技術がE.T.H.を反証したと発表。P vs. NP自体は未解決のままだが、計算が劇的に効率化する可能性が開けた。
「PとNPが直感に従うなら、両者は絶対に等しくないはずだ」と、Massachusetts Institute of Technologyの工学・計算機科学教授Ryan Williams氏は語った。
HNでの議論
22- fsmv
旧聞だし、ETHの証明にはP vs NPやその他実用的なことには全く何の含意もない
- peri-cl
あとこれも
https://news.ycombinator.com/item?id=50251661 (「指数時間仮説は偽である [pdf] (github.com/openai)」、309コメント)
- matt3210
IPO狙いの釣り