1が0より高くつくとき、圧縮は難しくなる

テキストをコンパクトに保存したり送ったりするには、各記号に0と1からなる語を割り当てる。頻繁に出る記号には短い語を、まれな記号には長い語を与える。これらの語は接頭符号（prefix code）をなさなければならない。つまり、どの語も別の語の先頭部分になってはならない。{0, 10, 11}はよいが、{0, 01, 11}はだめだ。0が01の先頭になっているからだ。接頭符号なら、長いビット列を区切り記号なしで語に切り分け直せる。

そうした符号のうち最良のもの、すなわち平均の長さが最も短いものは、1952年にD. A. Huffmanが見つけた。単純な貪欲法による手順で、高速に動く。

文字に値段があるとき

ハフマンの手順は、0と1のコストが同じだと仮定している。そうでないとしよう。1のほうが送信に時間がかかる、あるいは保存に場所をとるとする。すると各語のコストはその文字のコストの和になり、語の長さと同じくらい、その構成が重要になる。たとえばコストが1と3なら、00と01は同じ長さだが、コストは2と4になる。

この変種には長い歴史がある。R. M. Karpは1961年に、これを整数計画問題として定式化した。その後の研究で、整数のコストの組がどれであれ固定されていれば使える、厳密で効率的なアルゴリズムが見つかり、望むだけ最適値に近づける近似スキームも見つかった。だが、コスト自体が入力の一部である場合、問題がどれほど難しいかは誰も知らなかった。2021年になっても、まだ未解決問題として挙げられていた。

答えはNP完全

ベンガルールにあるインド理科大学院（Indian Institute of Science）のL. Sunil ChandranとPramaana LabsのRishikesh Gajjalaは、コストがK以下の符号が存在するかどうかを判定する問題がNP完全であることを証明した。2つのコストが連続する整数MとM + 1であっても、そうなのだ。計算機科学者は、ある問題が古典的な問題の一族全体と同じくらい難しいとき、それをNP完全と呼ぶ。そのうち1つに対する高速な一般的方法があれば、すべてに対する高速な方法が得られることになるが、そうした方法は知られていない。したがって、最も安い符号を見つけることはNP困難である。

コストを固定した場合の高速なアルゴリズムと矛盾するわけではない。証明では、Mは入力とともに大きくなる。あらかじめ固定したどのコストの組に対しても、それらのアルゴリズムは引き続き使える。

符号の木に隠されたパズル

証明の出発点は、難しいことが知られている問題だ。紙の上に交差なしで描かれたネットワークで、どの2つも結ばれていないk個の点を選べるか。証明は、最も安い符号がこの問いに答えるような符号化問題を組み立てる。

どの接頭符号も木で表せる。0は左へ、1は右へ進む。文字のコストがMとM + 1のとき、深さdで1をz個含む語のコストはM × d + zになる。深さがコストの大きな部分を、1の個数が小さな部分を決める。
著者らは新しい中間問題を考案した。木の各深さにある葉の数を固定し、葉がどこにあるかを採点する問題だ。そして、安い木は1段ずつ伸びていく過程で、小さなプログラムを実行しなければならないことを示した。そのプログラムは選ばれた点を1つずつ確かめ、それぞれの選択を書き写し、すべての結びつきを検査する。近道をすれば少なくとも1単位余計にかかり、点を1つ選ぶごとにちょうど1単位節約できる。
最後に、各記号が正しい深さに置かれるよう頻度を調整する。すると、その得点は符号化のコストに一定の量を加えたものになる。

論文の小さな例が、コストがいかに微妙かを示している。3つの記号の頻度は20、12、9で、文字のコストは83と84だ。符号(0, 10, 11)のコストは5,176。符号(1, 00, 01)のコストは5,175になる。高いほうの文字を最も頻度の高い記号に与えたほうが得をするのだ。残り2つの語に含まれる1が少なくなるからである。

難しさが潜む場所

2つ目の結果は、ごく普通の符号化の内部に難しさの所在を突き止める。ハフマンの手順は、最短の平均の長さを高速に見つける。だが、その長さを達成するすべての符号のうちで、頻度で重み付けした1の個数が最も少ないものを選ぶ問題も、やはりNP完全なのだ。

未解決の問いも残る。すべての数が小さいときにも問題が難しいままかどうか（いわゆる強NP困難性）、そして、任意の精度で最適値を近似でき、その実行時間が精度に対しても無理なく増えるような高速スキームが存在するかどうかだ。

AIとともに見つけた証明

論文は、証明がどのように得られたかを明記している。著者らはまず、OpenAIのCodexに、より一般的な問題の困難性の証明を求めた。次にそれを非二元符号へ、最後に二元符号へ拡張するよう求めた。Codexは帰着の戦略とその数学的な展開に貢献し、執筆や論証の確認、例の作成も手伝った。著者らは作業を導き、修正と簡略化を求め、説明を大幅に書き直したうえで、最終的な主張と証明に責任を負っている。他のプレプリントと同様、この論文はまだ査読を受けていない。