指数時間仮説（ETH）

問題の中には、ほとんどすべての可能性を試してみる以外に解く方法がないものがあります。指数時間仮説（英語では Exponential Time Hypothesis、略して ETH）は、ある特定の問題については、どれほど工夫してもそれ以外の方法はないだろう、という計算機科学者たちの「賭け」です。もっと速い方法は存在します。しかし最良の方法でさえ、問題の大きさに対して指数関数的に増える数のステップが必要になる、というのです。

ETH は P 対 NP 問題と深く関係しています。この問題については別の記事で解説しています。まだ読んでいない場合は、先にそちらを見てください。この記事はその内容を土台にしています。特に、アルゴリズムの計算量とは何か、そして n² と 2ⁿ の間にどうしてこれほど大きな隔たりがあるのか、という点です。

パーティーに誰を招くか

パーティーを開くことになり、4人の友だち、拓也さん、純さん、佳奈さん、大輔さんを招きたいとします。困ったことに、4人の間にはいろいろな人間関係があり、全員に気持ちよく過ごしてもらいたいと考えています。あれこれ聞いて回った結果、次の6つの条件が出てきました。

拓也さんか佳奈さんが来る（2人とも来てもよい）。
純さんと佳奈さんは仲が悪いので、2人そろって来ることはない。
大輔さんは、純さんも来る場合に限って来る。
拓也さんが来るなら、佳奈さんか大輔さんも来なければならない。
拓也さんと佳奈さんが2人とも来るなら、純さんも来なければならない。
拓也さん、純さん、大輔さんの3人のうち、少なくとも1人は来る。

すべての条件を同時に満たすには、誰を招けばよいでしょうか。自分で考えてみましょう。答えは記事の最後に載せてあります。

計算機科学者なら、この問題を命題論理の言葉に書き直すでしょう。友だち1人ひとりに文字を1つずつ割り当てます。文字は名前をローマ字で書いたときの頭文字で、例えば拓也さん（Takuya）は T です。各文字は真（拓也さんが来る）か偽（拓也さんが来ない）のどちらかです。記号 ∨ は「または」、¬ は「〜でない」と読みます。すると、1つ目の条件は次のようになります。

$T \lor K$

2つ目の条件は、「純さんが来ない、または佳奈さんが来ない」ということです。

$\neg J \lor \neg K$

3つ目の条件は間違えやすいので注意しましょう。「大輔さんは、純さんも来る場合に限って来る」とは、大輔さんが来て純さんが来ない、ということが起こってはいけないという意味です。つまり、大輔さんが来ないか、純さんが来るかのどちらかです。

$\neg D \lor J$

残りも同じように書き直します。問題全体は次のようになります。

$\begin{array}{rcl} 1. & T \lor K \\ 2. & \neg J \lor \neg K \\ 3. & \neg D \lor J \\ 4. & \neg T \lor K \lor D \\ 5. & \neg T \lor \neg K \lor J \\ 6. & T \lor J \lor D \end{array}$

条件どうしがよく似ていることに注目しましょう。どれも、いくつかの文字（記号 ¬ が付いたものもあります）を「または」でつないだ形をしています。しかも、文字が3つより多い条件は1つもありません。このような条件が与えられ、すべてが同時に成り立つように各文字に真と偽を割り当てる問題を 3-SAT といいます。3は各条件の文字が3つ以下であることを表し、SAT は英語の satisfiability（充足可能性）の略です。

一見すると、パズルコーナーの遊びのように思えます。しかし、実用的な問題の非常に多くを 3-SAT の形に書き直すことができます。授業の時間割づくり、プロセッサのチップが正しく計算するかどうかの検証、勤務シフトの計画、数独などです。その場合、文字は4つではなく、数百万にもなることがあります。

試すべき場合の数はいくつか

最も素朴な方法は、すべてを試すことです。拓也さんが来るか来ないかで2通りです。そのそれぞれについて純さんが来るか来ないかを考えると、もう4通りになります。友だち4人の場合の数は次のとおりです。

$2 \cdot 2 \cdot 2 \cdot 2 = 2^{4} = 16$

P vs. NP の記事で2進ベクトルを扱ったときも、同じように考えました。文字が n 個あれば、真と偽の割り当て方は 2ⁿ 通りあります。友だち4人なら16通りなので、数分で調べ終わります。文字が100個なら

$2^{100} ≒ 1.27 \cdot 10^{30}$

通りです。1秒間に10億通りを試せるコンピューターでも、宇宙が存在してきた時間のおよそ3,000倍の時間がかかります。

ところが逆は簡単です。「この3人を招けばいい」と言われたら、すぐに確かめられます。6つの条件を順に見て、それぞれが成り立つかどうかを調べるだけです。解を見つけるのは難しいのに、確かめるのは簡単です。P vs. NP の記事では、まさにこのような問題を NP というクラスに分類しました。

ただし、3-SAT は NP の中のありふれた問題ではありません。1971年に、NP のすべての問題を 3-SAT に変換できることが示されました。つまり、3-SAT を速く解ける人がいれば、速く確かめられる問題はすべて速く解けることになります。このような性質をもつ問題を NP 完全といい、3-SAT はその最も有名な例です。

2ⁿ より速く解けるか

解けます。すべてを試す必要はありません。例えば、拓也さんが来ない場合を考えると、1つ目の条件からすぐに、佳奈さんが来なければならないことがわかります。2人とも来ない場合は、まとめて除外できます。賢いアルゴリズムは、このような工夫をたくさん組み合わせています。現在知られている最良のアルゴリズムに必要なステップ数はおよそ

${1.307}^{n}$

です。これは大きな進歩です。n = 100 なら、10³⁰ ではなくおよそ 4.2 · 10¹¹ ステップで済み、コンピューターなら数分で終わります。

ただし、落とし穴があります。1.307ⁿ もやはり指数関数です。底を2から 1.307 に小さくしましたが、変数 n は指数に残ったままです。n がさらに大きくなれば、結局はこの増え方に押しつぶされてしまいます。n = 1000 では、1.307ⁿ でさえ117桁の数になります。

では、指数関数的でないアルゴリズムとはどのようなものでしょうか。例えば、n³ ステップで済むアルゴリズムです。これは多項式時間のアルゴリズムで、そうなれば 3-SAT はクラス P に属することになります。ところが、多項式と指数関数の間にはグレーゾーンがあります。どんな多項式よりも速く増えるのに、どんな指数関数よりも遅く増える関数です。例えば次の関数です。

$2^{\sqrt{n}}$

この関数の指数にあるのは、n の平方根だけです。4つの関数を表で比べてみましょう。

n	n³	$2^{\sqrt{n}}$	1.307ⁿ	2ⁿ
20	8000	22	212	1,048,576
100	10⁶	1024	4.2 · 10¹¹	1.3 · 10³⁰
1000	10⁹	3.3 · 10⁹	1.9 · 10¹¹⁶	1.1 · 10³⁰¹

n = 1000 のとき、 $2^{\sqrt{n}}$ は n³ と同じくらいの大きさですが、2つの指数関数は呼び名すらない大きさの数まで飛んでいってしまいます。 $2^{\sqrt{n}}$ のように、1より大きいどんな底 c に対しても cⁿ より遅く増える関数を準指数的な関数といいます。

グラフを見ても同じことがわかります。縦軸は対数目盛りで、1目盛り上がるごとに数が10万倍になります。そうしないと、2ⁿ 以外は図に収まりません。

$2^n（赤）、1{,}307^n（オレンジ）、2^{\sqrt{n}}（青）、n^3（緑）の増え方。縦軸は対数目盛り$

このようなグラフでは、指数関数は右上がりの直線になります。赤の 2ⁿ はオレンジの 1.307ⁿ より傾きが急ですが、どちらも直線です。おもしろいことに、オレンジは最初のうち緑の n³ より下にあります。n = 42 あたりで緑を追い越し、その後は二度と下に戻りません。一方、青の $2^{\sqrt{n}}$ は曲がっていき、下のほうで緑の近くにとどまります。

ETH の正確な主張

いよいよ仮説を述べることができます。1999年に Russell Impagliazzo と Ramamohan Paturi が定式化しました。

1より大きいある数 c が存在して、n 個の文字をもつ 3-SAT を、およそ cⁿ ステップより速く解くアルゴリズムは存在しない。

わかりやすく言うと、どういうことでしょうか。指数関数の底は、工夫によって2から 1.5、1.307 へと小さくでき、いつかは 1.2 まで下がるかもしれません。しかし、いくらでも1に近づけることはできない、ということです。どこかに越えられない限界があります。したがって ETH が正しければ、計算量が $2^{\sqrt{n}}$ のアルゴリズムは存在しないはずです。

なぜ「仮説」なのでしょうか。誰も証明できていないからです。ETH は作業上の仮定で、P vs. NP の記事で P ≠ NP を仮定したのと似ています。ほとんどの計算機科学者は ETH を信じています。何十年にもわたる努力でも、底が2から少しずつ下がってきただけだからです。しかし、証明を手にしている人はいません。

ETH と P vs. NP

この2つの問題はどう関係しているのでしょうか。3-SAT には何らかの「本当の」難しさ、つまり考えうる最速のアルゴリズムがあると考えてみましょう。それは次の3つの領域のどれかにあります。

3-SAT の難しさの3つの領域：多項式（緑）、準指数（青）、指数（赤）

緑の領域：多項式。 3-SAT は例えば n³ ステップで解けます。3-SAT は NP 完全なので、このとき P = NP が成り立ち、ETH はもちろん成り立ちません。
青の領域：準指数。 3-SAT は $2^{\sqrt{n}}$ ステップかそれに近い手間で解けます。多項式時間では解けないので P ≠ NP が成り立ちます。しかし ETH は成り立ちません。
赤の領域：指数。 cⁿ より速くは解けません。ETH が成り立ち、したがって P ≠ NP も成り立ちます。

図からわかるように、ETH は P ≠ NP よりも強い主張です。3-SAT が多項式時間で解けないだけでなく、準指数時間でも解けないと言っているからです。ETH を証明した人は、同時に P ≠ NP も証明したことになり、100万ドルの賞金を手にするでしょう。

逆に、ETH を否定した人が P = NP まで証明したことになるとは限りません。青の領域のアルゴリズムを見つければ十分だからです。このことを覚えておきましょう。すぐあとで使います。

ETH は何の役に立つか

ある問題が速く解けないことを証明するのは、計算機科学ではとてつもなく難しいことです。そのような結果はほとんど得られていません。ETH はここに抜け道を与えてくれます。「問題 X は難しい」の代わりに、「ETH が正しければ、問題 X は難しい」を証明するのです。

どうやって証明するのでしょうか。もし問題 X が速く解けるなら、3-SAT も速く解けることを示します。例えば次の問題を考えましょう。n 人の人がいて、そのうちのいくつかの組は仲が悪いことがわかっています。そのような組が同じ部屋にならないように、全員を3つの部屋に分けたいとします。計算機科学者はこれをグラフの3彩色と呼びます。どんな 3-SAT の問題からも、人数が文字の個数の数倍にしかならないように、この問題を作ることができます。したがって、人を部屋に分ける問題が準指数時間で解けるなら、3-SAT も準指数時間で解けることになり、ETH は崩れます。

このような条件付きの結果は、今では数百もあります。個々の問題が正確にはどれくらい難しいのかを調べる研究分野全体が、家が土台の上に建つように、ETH の上に成り立っています。

ETH には、より強い「姉妹」もあります。強指数時間仮説（SETH）です。こちらは、条件が3つより多くの文字、例えば10個や100個の文字を含んでもよい問題を扱います。SETH は、条件を長くすればするほど、達成できる最良の底が2に近づくと主張します。つまり、長い条件の場合には、2ⁿ 通りをすべて試す愚直な方法に比べて、ほとんど何も節約できないということです。

なぜ今 ETH が話題なのか

ChatGPT で知られる OpenAI は、2026年10月にプレプリント、つまりまだ査読を経ていない論文を公開しました。タイトルは The Exponential Time Hypothesis is False、日本語にすると「指数時間仮説は偽である」です。その中で OpenAI は、3-SAT をおよそ

$2^{\frac{n}{\sqrt{\log n}}}$

ステップで解くアルゴリズムを見つけたと主張しています。つまり、指数にあるのは n そのものではなく、n を（自然）対数の平方根で割ったものです。この分母はとてもゆっくりとしか増えませんが、それでも増えていきます。そして、関数が準指数的になるには、それで十分なのです。さらにこのアルゴリズムは、解を1つ見つけるだけでなく、解がいくつあるかを数えることもできるそうです。

もしこれが正しければ、OpenAI のアルゴリズムは上の図の青の領域に入ります。それは何を意味するのでしょうか。

ETH は崩れ、SETH も、それらの上に成り立っていた数百の条件付きの結果も一緒に崩れます。計算機科学者は「ETH が正しければ…」という結果の多くを捨てるか、書き直さなければならなくなります。
P 対 NP 問題は解決しません。このアルゴリズムはやはり多項式時間ではないからです。
実用面では、ほとんど何も変わりません。式には値のわからない定数が隠れています。仮にそれらが1だとすると、n = 1000 では $\sqrt{\log n}$ はおよそ 2.6 になり、およそ 2³⁸⁰ ステップとなります。これは、現在の最良のアルゴリズムの ${1.307}^{1000} ≒ 2^{386}$ とほとんど変わりません。新しいアルゴリズムが現在のアルゴリズムを大きく上回るのは n がさらに大きいときで、どれだけ上回るかは、まさにその未知の定数しだいです。したがって、主に理論的な意味をもつ結果です。暗号や銀行のシステムには影響しません。

現時点では、まだ検証されていない主張です。証明は長く技術的で、専門家たちはようやく読み始めたところです。未解決問題を解いたという大きな発表が、誤りだったとわかったことは過去に何度もあります。今のところは、専門家の判断を待つことにしましょう。この段落は2026年10月27日に書いています。

パーティーの問題の答え

招くのは拓也さん、純さん、大輔さんで、佳奈さんは招きません。図には16通りすべてを示しています。各列が1つの場合を表し、塗りつぶした丸はその友だちが来ること、白い丸は来ないことを表します。列の下の赤い数字は、成り立たない最初の条件の番号です。すべての条件が成り立つ唯一の場合を、緑の枠で囲んでいます。

誰を招くかの16通りすべて。行は友だち T、J、K、D に対応し、塗りつぶした丸は来ることを表します。

そしてこれこそが、ETH がほとんど乗り越えられないと考える総当たりの方法です。友だち4人なら16列ですが、友だち100人なら、人間の体にある原子の数よりも多い列が必要になります。

« 前へ: 情報科学最大の難問：P 対 NP 問題

次へ: トラクテンバーグ・システムによる速い足し算 »