海外の反応
2026年10月27日
【海外の反応】指数時間仮説を反証した論文に数学者ら激論
理論計算機科学の分野で、SAT問題が指数時間より速く解けないとする「指数時間仮説(ETH)」を反証したとする論文が公開され、海外の技術者向けフォーラムで話題になった。3-SATが準指数時間で解けることを示す内容で、P対NP問題との関連から「P=NPに一歩近づいたのでは」との声が上がった一方、スレでは「準指数時間と多項式時間の間には大きな差がある」「一般のNP問題に拡張できるわけではない」と冷静な指摘も相次いだ。著名な計算機科学者スコット・アーロンソン氏がP=NPの可能性を3%から5%に上げたというコメントも紹介され、議論を呼んだ。
指数時間仮説は偽である [PDF]
出典: github.com / 元記事はこちら
2
海外の名無しさん
2026-10-26 23:43
すごいし予想外の結果だ。ただ誤解しないでほしいのは、これはNP全体が準指数時間で解けることを意味するわけじゃないという点。論文にも書いてある通り、「2^o(n)という形の実行時間の上界は、一般の多項式時間帰着では保存されない(そのためには2^n^o(1)が必要)。したがって今回の結果は、NP問題全般が準指数時間アルゴリズムを持つことを意味しない」とのことだ。
11
海外の名無しさん
2026-10-26 23:49
>>2 もう少し詳しく説明してもらえる?
31
海外の名無しさん
2026-10-26 23:56
>>11
P=NPなら 3SATには多項式時間アルゴリズムが存在する
P≠NPなら 3SATに多項式時間アルゴリズムは存在しない
ETHが真なら 3SATに準指数時間アルゴリズムは存在しない
ETHが偽なら 3SATには準指数時間アルゴリズムが存在する
——
ETHが真 → P≠NP
ETHが偽(!!!) → P=NPかどうかは依然未解決
3
海外の名無しさん
2026-10-26 23:37
うわ、計算量クラスの分離が示されるなんて本当に稀なことだ。SATソルバーの専門家に聞きたいんだけど、この論文の手法に何か即効性のある応用はあるんだろうか。それとも実際のSATソルバーはそもそも最悪時間とはかなり縁遠い動きをしていて、これは実用には乗せにくい理論上のアルゴリズムという話なのかな。
12
海外の名無しさん
2026-10-26 23:59
>>3 ハッシュテーブルと同じで、SATソルバーに入力するデータの性質が実際の性能に大きく影響する。現実の入力は病的なケースよりずっと素直な傾向があるから、実用的な応用はそれほど無いと思う。でもまだ論文は読んでないんだけどね。
5
海外の名無しさん
2026-10-26 23:03
これはかなり大きな話に見える。P=NPそのものじゃないけど、同じレベルの話というか。何か見落としてる?
17
海外の名無しさん
2026-10-26 23:27
>>5 準指数時間と言っても、多項式時間よりずっと大きい場合もある。その2つの間には大きな隔たりがあるよ。
18
海外の名無しさん
2026-10-26 23:14
>>5 (あくまで素人の解釈だけど)これはP≠NPへの確信を弱めるものだと思う。この分野の専門家に、それが正しいかどうか聞いてみたい。
20
海外の名無しさん
2026-10-26 23:08
>>5 「P=NPに近いけどそうじゃない」んじゃなくて、実際にP=NPではないんだよ。それでも、すごい成果だけど。
6
海外の名無しさん
2026-10-26 23:12
理論計算機科学の授業で居眠りしてた人向けに、誰かETHを子供でもわかるレベルで説明してくれない?友達のために聞いてるんだけど…
25
海外の名無しさん
2026-10-26 23:15
>>6 3SATは準指数時間では解けない、というのがETH。ちなみに個人的には、昔からこれ、名前の付け方がイマイチだと思ってた。
7
海外の名無しさん
2026-10-26 23:41
NPがいつもより少しPっぽく見えてきたな
10
海外の名無しさん
2026-10-26 23:20
『AIは所詮ストキャスティック・パロット』派、死屍累々。
28
海外の名無しさん
2026-10-26 23:37
>>10 数学専攻なんだけど、この論文まったく読めない…
13
海外の名無しさん
2026-10-26 23:41
>>4 いや違う。SETHが真なら二乗時間が下限になる、というだけで、SETHが偽だからといって二乗時間の下限が無くなるわけじゃない。
32
海外の名無しさん
2026-10-26 23:44
>>13 でもそれって…可能性はゼロじゃないってことだよね
46
海外の名無しさん
2026-10-26 23:54
>>32 確率はちゃんと数字で言おうよ。君がこの先数分でくも膜下出血を起こして、俺のコメントを読めなくなる可能性だってゼロじゃない。まあそうなったら、頑張ったとは言っておく。
47
海外の名無しさん
2026-10-26 23:54
>>32 皮肉じゃなくマジでそれ。
14
海外の名無しさん
2026-10-26 23:47
>>4 SETHはETHよりずっと強い主張だよ
26
海外の名無しさん
2026-10-26 23:50
>>9 これは数学者向けに書かれた数学の論文だから、その分野の専門家じゃない人が理解するのはまず無理。もっと初歩的な説明があれば別だけど、たぶんそんなものは存在しない。
27
海外の名無しさん
2026-10-26 23:47
>>9 難しいものはたまに、本当に難しいんだよ。
34
海外の名無しさん
2026-10-26 23:20
>>15 k-SATが2^{o(n)}で解けないという結果は明らかにP≠NPを意味すると思うけど、ETHがなぜNP=EXPを意味するのか、そして¬ETH(ETHが偽であること)がなぜNP≠EXPを意味するのかが分からない。
49
海外の名無しさん
2026-10-26 23:22
>>34 「ETHがNP=EXPを意味する」という部分は僕の間違いだったので、ETHが真の場合にNP=EXPを意味するという記述は編集で削除した。ただ、仮説が偽である今回のケースでは、NPがEXPの真部分集合であることがNP≠EXPを意味する。
35
海外の名無しさん
2026-10-26 23:26
>>16 これはNP全体が準指数時間だということを意味するわけじゃなく、3SATがそうだというだけ。他の問題への変換を挟むと、結局指数時間になることもある。
50
海外の名無しさん
2026-10-26 23:30
>>35 いや違う。NPの問題は常に多項式時間で3SATに帰着できるよ。
56
海外の名無しさん
2026-10-26 23:38
>>50 論文のこの記述を見てほしい。「2^o(n)という形の実行時間の上界は、一般の多項式時間帰着では保存されない(そのためには2^n^o(1)が必要)。したがって今回の結果は、NP問題全般が準指数時間アルゴリズムを持つことを意味しない」
57
海外の名無しさん
2026-10-26 23:56
>>50 帰着の方向を逆にしてない?それとも、君の言いたいことを僕が誤解してるだけ?
36
海外の名無しさん
2026-10-26 23:37
>>18 スコット・アーロンソンが自身のブログでコメントしている。「このニュースを受けて、私個人のP=NPである確率の見積もりを3%から5%に上げる」とのこと。
51
海外の名無しさん
2026-10-26 23:45
>>36 スコットほど頭は良くないけど、自分の感覚だと10%から20%くらいに上がった感じ。これって賭けの予測市場とかあるの?
39
海外の名無しさん
2026-10-26 23:18
>>18 これが言ってるのは基本的に「NPはEXPと同じではない」ということだけだよ
40
海外の名無しさん
2026-10-26 23:23
>>19 P≠NPで、かつこのNP≠EXPの証明が正しいと仮定すると、次に「自然」な候補としてNPの下限はどのくらいの速さで増大するべきなんだろう?この論文はΩ(2^(n/√(log n)))くらい(多少の補正項付き)を示しているように見えるけど、それだとかなり期待外れな答えになる。
52
海外の名無しさん
2026-10-26 23:44
>>40 それはP=NP側に天秤を少し傾ける要素だね!
41
海外の名無しさん
2026-10-26 23:47
>>22 「2n」は「2^n」の誤記だと思う
53
海外の名無しさん
2026-10-26 23:53
>>41 スレ主がもうP=NPを解決してるなら別だけどね…
44
海外の名無しさん
2026-10-26 23:19
>>25 *「解ける」の方が正しい。これはEXP≠NPを証明するものだよ
55
海外の名無しさん
2026-10-26 23:21
>>44 頼まれた通りに(ETHの)予想の内容を述べてるだけだよ
45
海外の名無しさん
2026-10-27 00:01
>>31 いや、それは分かってるんだけど、3SATが準指数時間で解けることを証明しても、なぜ他のNP完全問題全部がそうなるとは言えないのかが分からない。どれも多項式時間で3SATに帰着できるはずなのに。
48
海外の名無しさん
2026-10-26 23:53
>>33 最後の編集について、もう少し詳しく説明してもらえる?
58
海外の名無しさん
2026-10-26 23:50
>>56 一方で、この手の手法が他のNP問題に全然応用できないとしたら、それはそれで意外な話だと思う。
59
海外の名無しさん
2026-10-26 23:49
>>56 おお、それは面白いし意外だ。指摘してくれてありがとう。
この話題の背景と論点
指数時間仮説(ETH)は、SAT問題の代表格である3-SATが指数関数的な時間をかけなければ解けないとする、計算複雑性理論の前提のひとつ。P対NP問題そのものは未解決のままだが、ETHは多くのアルゴリズムの下限を導く土台として広く使われてきた。今回の論文が示したのは、3-SATを「準指数時間」で解くアルゴリズムの存在で、これはP(多項式時間)よりは遅いが、従来想定されていた指数時間よりはるかに速い。読者が誤解しやすいのは、この結果が直ちにP=NPを意味するわけではない点だ。スレでも繰り返し指摘された通り、3-SATで成立した結果は、他のNP問題への帰着を通じて一般化できるとは限らない。それでも複雑性クラスの分離を扱う結果自体が極めて稀であり、著名な研究者がP=NPの可能性の見積もりを上方修正するなど、理論計算機科学者の間でも衝撃をもって受け止められている。
※本記事は海外掲示板 Hacker News のスレッド「The Exponential Time Hypothesis Is False [pdf]」から抜粋し、編集部で日本語に意訳したものです。訳文の責任は当サイトにあります。
この記事のリアクション
まだコメントはありません。