還元は難しさを運ぶ — NP 完全と「速く解けない」の意味

手元で測りました(Python 3.14.6 / macOS 26.5.2 arm64、2026-10-07)。要素は全部偶数で、目標は奇数です。したがって解はなく、全部の組を必ず調べます。

n   2^n       time_s      ratio_to_prev
10  1024      0.0003
11  2048      0.0006      2.17
20  1048576   0.5767      2.10
21  2097152   1.2183      2.11
22  4194304   2.5566      2.10
 
n=22  check ok=True  per-check 0.80 microseconds  (reads 11 elements)

n=10〜22 で、時間の比は 2.09〜2.27(中央値は約 2.1)でした。2 を少し超えるのは、1組ごとに n 個を足すからです。秒数は機械で変わるので、見るのは倍率です。検算は n=22 でも1回 1μs 未満でした。

この「全部をどれかに言い換える」を、Cook が 1971 年(STOC '71)、Karp が 1972 年に発表しました。Levin の論文の刊行は 1973 年です(Clay は、Cook と Levin が 1971 年に独立に定式化したと書きます)。Cook の Summary の趣旨はこうです。非決定性の多項式時間で解ける認識問題はどれも、命題論理式についての1つの問題へ還元できる。Karp は21問題の一覧(SATISFIABILITY、CLIQUE、KNAPSACK、PARTITION、DIRECTED HAMILTON CIRCUIT など)を挙げ、こう書きました。

We proceed to give a series of explicit reductions, showing that SATISFIABILITY is reducible to each of the problems listed.

Levin について、Cook は Clay の問題記述でこう書いています。「independently of Cook and Karp, defined the notion of “universal search problem”」。そして結論は、今も次の一文です。

Most complexity theorists believe that P ≠ NP.

最短路と最長単純閉路。 最短路には、負の閉路が無い場合、多項式時間で解ける手法があります(この期の第8・9回で扱いました)。問いを「同じ頂点を2度通らない、最も長い閉路」に変えます。辺の重みを全部1にして「長さが頂点数 V の単純閉路があるか」と問うと、全頂点を1度ずつ回る閉路があるか、つまり Karp の一覧の10番 UNDIRECTED HAMILTON CIRCUIT そのものです。還元の向きで読むと、最長単純閉路は少なくともこれと同じだけ難しいことになります。

依存の解決。 Russ Cox の「Version SAT」(2016-12-13)はこう書き出します。

Dependency hell is NP-complete. But maybe we can climb out.

本文では「the version selection problem is NP-complete」と書き、3-SAT からの還元を自分で示しています。Cox は、Debian と RedHat の NP 完全性の証明が EDOS の報告書(2005)にあるとも紹介しています。プロジェクト側の Web 版には次の定理文があります(報告書の PDF 本体は未取得)。

Theorem 1 Checking whether a single package P can be installed, given a repository R, is NP-complete.

Cox は、前提の側を変える道も示しています。

what if, instead of allowing a dependency to list specific package versions, a dependency can only specify a minimum version?

Go の MVS は、この形で動きます。go.dev/ref/mod の説明はこうです。

MVS starts at the main modules (special vertices in the graph that have no version) and traverses the graph, tracking the highest required version of each module.

これはグラフの巡回です(第11期の『依存はグラフ — import が解決される形』で見た形です)。ただし、このページに NP の語はありません。「Go 公式が NP を避けた」とは書けません。