NP困難問題は実は解ける？「理論と実践の違い」を実例で解説

この記事は、実際に使われている一番の解決策についてあまり触れていない気がする

難しいものを許可しない

依存関係マネージャは、NP困難な空間全体を事実上排除するような、膨大なカテゴリの状況をただブロックする傾向がある

型システムも同様に、明確に区切られている

秘訣は「とにかくやる」ということではなく、まあ定義上やらざるを得ないのだが、一般的な問題は「不可能」であることを認識して、最善を尽くすか、不可能なものを排除し始めるかのどちらかだ

まったくその通り！NP困難な問題を難しくしているのは、ほとんど常に特定の問題構成に関連する組み合わせ爆発だ。近似ヒューリスティックや分枝限定ソルバーを与えれば、指数関数的な爆発を引き起こすインスタンスを構築できる。しかし、ほとんどの実用的な問題では、そうした爆発的な構成には到達しない。

NP困難な問題の特定のクラスについて、ある意味でこれを定量化できるかもしれない。

興味深いのは、多くのアルゴリズム（特に暗号技術）が、そうした組み合わせのエッジケースを意図的に作り出していることだ。SATソルバーは、生活やプログラミングで発生する普通の問題を見れば素晴らしい仕事をする。SHA256を見るSATソルバーは、そうでもない。実際、暗号システムを開発する科学は、ヒューリスティックな近似に耐性のある指数関数的爆発を見つける科学であると言えるだろう。

>(1)と(2)については、最悪ケースは実際には発生しない。つまり、パッケージのインストールや型チェックは確かに遅くなりうる。しかし、少なくとも私のキャリアでは、銀河規模の爆発を見たことがない。

NP困難な問題は厳密に解くのは難しいが、通常はかなり良い近似解を効率的に得ることが可能だ。しかし、いくつかの探索問題は、近似でさえ非常に難しい。aptitudeで古いDebianインストールをメジャーアップグレードしたことがあるなら、それが定期的に外側の探索空間の深くで迷子になるのを見たことがあるだろう。

時々、aptitudeは正しい解に到達するために、パッケージをダウングレードしたり、アンインストールしたり、推奨パッケージをインストールしない必要がある。ダウングレードを試みる可能性のあるパッケージは多数あり、それぞれが新しい可能性を持つまったく新しい混乱を生み出す。これは他のパッケージマネージャでは得られないものであり、その探索戦略は、すべての困難を生み出す小さなパッケージ群を手動で特定しようと手助けしない限り、本当に手に負えない。

TFAの精神に沿ったこの頭の体操が好きだ：「巡回セールスマン問題は、ある大きなグラフのクラスではO(N)であることをご存知でしたか？」

もう一つの洞察：私は、巧妙なO(logn)解が、ほぼ分岐のないO(N)の事前パスと、連続メモリアクセスやベクトル演算のようなコンピュータが好む問題によって、定期的に粉砕されることを発見する。

> NP困難な問題は理論的には解けるが、実際には絶望的に高価だ。良いアルゴリズムが存在しないことは基本的に証明されている。少なくとも私はそう受け取った。

あなたは間違ったことを受け取った。理論は、_すべての_可能な入力に対して良いアルゴリズムが存在しないことを教えている。これは、問題空間の部分集合に自分を制限し、ヒューリスティックを使って残りの病的なケース（もしあれば）を隅に追いやり、それが実際にはあまり頻繁に発生しないことを監視し確保する必要があることを意味する。

パッケージマネージャは、この記事が伝えるように、NP困難性_にもかかわらず_ではなく、NP困難性_のために_、そのように設計されている。

依存関係解決の形式的モデルでは、3つの中核条件は次の通り：1) ルートパッケージが含まれる、2) 依存関係の閉包（必要なものがすべて存在する）

3) バージョンの一意性（パッケージ名ごとに最大1つのバージョン）

NPM、yarnなどは3)を落としており、NP困難ではなくなる。

Goは最小バージョン選択に制限しており、線形時間解を認めている。

Cargoは複数のメジャーバージョンを許可することで、3)のほとんどのケースを減らし、その後ヒューリスティックに頼って病的なケースを剪定し、比較的まれにしている。実際の世界のツリーで問題があったケースはあったが、そのタイプを捕まえるヒューリスティックを追加すると、最終的に非常にまれになる。このスタイルの設計は、既知のNP困難性のために採用されている。一般的なケースを解くアルゴリズムを探し回るのではなく、可能なところで問題を単純化し、[…]

私は電子設計自動化でキャリアを過ごした。そこでは、実質的にすべての興味深い問題がNP困難だが、それらを解くか、少なくとも近似的に解く必要があり、現実の問題はしばしば構造を持っているため、正しいアプローチで非常に大きな問題を理論的な複雑さにもかかわらず厳密に解くことができ、厳密解が見つからない場合でも、許容できる解となる適切な境界を見つけることがよくある。

営業担当者は、最適解を見つけることがNP困難であっても、旅行を計画しなければならない（一例を挙げると）。問題ない。まともなヒューリスティック手法がある。

面白いことに、今朝まさにLLMにNP困難な問題（ナップザック問題の変種）のアルゴリズムを実装するように頼んだ。2つの指示を与えた：

* 完璧なスコアを狙うNP解を実装しないで。最適解のx%以内に入る高速な解を実装して。

* 解が不可能に見えるか、時間がかかりすぎる場合は、見つけられる最も近い解と、その解が最適でないという警告を返して。

数分でコードが得られた。ランダムな入力のサンプルでは、アルゴリズムは約99.9%のケースで最適解の1%以内の解を生成する。p95実行時間は私のラップトップで2msをはるかに下回る。

それだけだ。本番システムに必要なのはそれだけだ。「十分に近い」を非常に速く得られれば十分で、不可能なケースはめったに発生しない。発生したとしても、単に回避策を講じればよい。