OpenAI、計算機科学の定説「指数時間仮説」を覆す

A.I. Just Blew Up a Key Tenet of Computer Science

OpenAI、計算機科学の定説「指数時間仮説」を覆す

「解くのは難しく、答え合わせは簡単」——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氏は語った。
  1. fsmv

    旧聞だし、ETHの証明にはP vs NPやその他実用的なことには全く何の含意もない

  2. peri-cl

    あとこれも

    https://news.ycombinator.com/item?id=50251661 (「指数時間仮説は偽である [pdf] (github.com/openai)」、309コメント)

  3. matt3210

    IPO狙いの釣り

この日のほかの記事

2026-11-17