2026/03/24 22:00
ミサイル防衛はNP完全問題です
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
Summary
米国の地上ベース中間弾道ミサイル防衛（GBMD）システムは、インターセプタ数が限られており、追跡失敗やデコイ使用時に苦戦します。
- 費用・在庫: 各地上ベースインターセプタ（GBI）は約 $75 百万ドルで、アラスカとカリフォルニアに44機配備されており、効果的単一射撃殺傷確率（SSPK）≈ 56％です。
- 殺傷確率: 4機の独立インターセプタを用いた理論上の殺傷確率は P(kill|4)=1−(1−0.56)^4 ≈ 96％です。実際には追跡確率で乗算されます: K_w = P(track) × [1−(1−SSPK)^n]。P(track)<0.98 の場合、4機が標的を殺傷する信頼度は80％未満になり、4–20の弾頭に対して 80 % 信頼度を確保するには P(track)>0.978 が必要です。
- 追跡への脅威: 敵はレーダー設置場所を破壊することで P(track) を低下させることができ、2026 年の最近の衝突では地域全体で追跡網が排除されました。
- 武器‑標的割り当て（WTA）: 各インターセプタを単一標的に割り当てる問題は NP 完全で、デコイが有効な標的数を増加させると指数関数的に難易度が上がります (W* = W·P_ww + D·P_dw)。
- アルゴリズムの進歩: Branch‑price‑and‑cut は、10,000 件の武器/標的を持つ大規模な WTA インスタンスを数分で解決できるようになり、以前は 400 件以上の武器で 2 時間後にタイムアウトしました。
- カバレッジ制限: 最適配分でも現在の 44 機の GBIs は約 11 個の ICBM（弾頭ごとに4機）しか防衛できません。20 個の弾頭を防衛するには ≈113 機が必要です (P(track)=0.99、SSPK=0.70)。
- シューティング・ルック・ショットドクトリン: この戦略は同じシナリオでインターセプタ数を 47 機に削減しますが、攻撃者は ⌊I/4⌋+1 個の弾頭だけで防衛側に各標的あたり4機未満を割り当てさせることができます (閾値＝12, I=44 の場合)。
- デコイの影響: デコイを追加するとインターセプタ要件が大幅に増加します（例：10 個の弾頭 + 10 個のデコイ → 73 機）。
- 代替兵器: 低コストオプションとして誘導エネルギーシステムが検討されていますが、滞留時間、プラットフォームカバレッジ、気象減衰により同様のスケール制約があります。
含意:
米国の防衛予算は追加インターセプタを調達しレーダー設置場所を保護するために増大し、ミサイル防衛産業は WTA 最適化ソフトウェアの複雑性が高まります。敵は追跡耐久性とデコイ対策技術への投資をさらに進める可能性があります。
本文
SSPK：単一インターセプタの性能はどれくらいか？
Single Shot Probability of Kill（SSPK） は、個々のインターセプタが1回の交戦で1つの弾頭を確実に攪乱できる確率です。
センサー精度・誘導精度・インターセプタ品質などを総合的に表します。
例として、米国の地上型ミッドコース防衛（GMD）システムは、Ground‑Based Interceptors (GBIs) を使用し、試験記録[3]からおよそ56 % のSSPK が推定されています。
各 GBI は約 7,500 万ドルで、2024 年時点でアラスカとカリフォルニアに44 台が配備されています。
確率を上げる：1つの弾頭に複数インターセプタを投入する
2 インターセプタで1つの弾頭を迎撃、2026 [11]
まず、インターセプタ失敗は独立していると仮定します。
つまり、一台が外れても他台が成功するかどうかには影響しません。
1 回のミス確率 は
[ P(\text{miss}) = 1-\text{sspk} ]
(n) 台を独立に発射した場合、全て失敗する確率は
[ P(\text{all miss})=(1-\text{sspk})^{,n} ]
従って、少なくとも1台が弾頭を攪乱できる確率は
[ P(\text{kill}\mid n)=1-(1-\text{sspk})^{,n} ]
米国 GMD の公開情報を用いれば (\text{sspk}=0.56)、(n=4) とすると
[ P(\text{kill}) = 1-(1-0.56)^{4}\approx 0.9625 \approx 96,% ]
独立性の仮定は楽観的で、実際には下記のように相関が生じる可能性があります。
すべてのインターセプタが同一追跡データに依存し、偽装弾を本物と誤認した場合、実際の攪乱確率はこの式より低くなります。
追加インターセプタでの殺傷確率の変化
| インターセプタ数 (n) | P(kill) |
|---|---|
| 1 | 56 % |
| 2 | 80.64 % |
| 3 | 91.48 % |
| 4 | 96.25 % |
| 5 | 98.35 % |
したがって、1 弾頭に対しては44 台のインターセプタで約 96 % の攪乱確率を期待できます。
ただし、この数値は楽観的です。
P(track)：SSPK が捉えられない要素
「見えないものは撃てない」。
上記式 (P(\text{kill})=1-(1-\text{sspk})^{,n}) は、すでに弾頭を検出し、追跡精度が十分で、正しく本物と分類され、指揮統制システムも機能しているという前提です。
実際にはこれらの段階全てが失敗する可能性があります。この場合、インターセプタを増やしても意味がありません。
Wilkening（1998）は、検出・追跡・分類・指揮統制パイプライン全体を表す確率 (P(\text{track})) を導入しました[5]。
総攪乱確率は
[ K_w = P(\text{track}) \times \bigl[1-(1-\text{sspk})^{,n}\bigr] ]
これは 共通モード因子 です。
ターゲットが検出されない、あるいは破片と誤分類された場合、割り当てられたすべてのインターセプタが失敗します。
したがって、前節の独立性仮定は「追跡成功」時に限定されます。
(P(\text{track})<1) の殺傷確率表
| インターセプタ数 (n) | P(track)=1.0 | P(track)=0.95 | P(track)=0.90 |
|---|---|---|---|
| 1 | 56 % | 53.20 % | 50.40 % |
| 2 | 80.64 % | 76.61 % | 72.58 % |
| 3 | 91.48 % | 86.91 % | 82.33 % |
| 4 | 96.25 % | 91.44 % | 86.63 % |
| 5 | 98.35 % | 93.43 % | 88.52 % |
(P(\text{track})=0.90) のとき、4 台で「96 % 攪乱確率」は実際には87 % 未満に低下します。
5 台でも89 % にしか達しません。
Wilkening の分析では、国防ミサイルが 80 % の信頼性で全弾頭を破壊するためには (P(\text{track})>0.978) が必要です。
それ以下では SSPK を改善しても十分とは言えません。
これは「検出・追跡・分類等のパイプラインがほぼ完璧に機能しなければならない」という非常に高い基準です。
したがって、前節で示した確率は最良ケースであり、実際には (P(\text{track})) が 1 未満であるため、実効攪乱確率は常に低くなります。
実務上の追跡問題
最近の出来事では、ミサイル防衛レーダーが積極的に攻撃され破壊されたケースが確認されています[7][8][9]。
これらのセンサーは数億ドル規模であり、破壊または劣化するとその地域全体の追跡網が消失します。
インターセプタを増やしても、追跡パイプラインが存在しない限り補えません。
さらに、1991 年のパトリオットミサイル失敗という史上最大級のソフトウェアバグも同様です。
システム時計の固定小数点切断誤差により追跡レーダーが誤った空域を観測し、スカッドミサイルは全く追跡されませんでした。28 名の兵士が死亡しました。インターセプタ自体は物理的に有効でしたが、(P(\text{track})) がほぼゼロだったためです。
複数弾頭を迎撃するケース
例として、I = 7 台のインターセプタ と W = 3 台の弾頭 を考えます。
(P(\text{track})) は除外し、理想化した場合のみ検討します。
- 弾頭 AA：大都市へ向かう
- 弾頭 BB：空港へ向かう
- 弾頭 CC：軍事基地へ向かう
| 割り当て | P(kill A) | P(kill B) | P(kill C) |
|---|---|---|---|
| 4 to AA, 2 to BB, 1 to CC | 96.25 % | 80.64 % | 56.00 % |
| 3 to AA, 3 to BB, 1 to CC | 91.48 % | 91.48 % | 56.00 % |
| 3 to AA, 2 to BB, 2 to CC | 91.48 % | 80.64 % | 80.64 % |
| 2 to AA, 2 to BB, 3 to CC | 80.64 % | 80.64 % | 91.48 % |
「最適」割り当ては、各ターゲットの価値に依存します。
これを大規模化すると、I = 444 台、W = 1515 台 といった極端なケースでは、すべての弾頭が異なる都市を標的とし、インターセプタごとの SSPK が幾何学・時間・タイプにより変動するため、割り当て可能性は組合せ的に爆発します。
武器‑ターゲット割り当て問題（WTA）
上記の割り当て問題には正式名称 Weapon‑Target Assignment (WTA) problem が存在します。
与えられるもの：
| 変数 | 説明 |
|---|---|
| (I) | インターセプタ（武器）の総数、インデックス (i=1,\dots,I) |
| (W) | 弾頭（ターゲット）の総数、インデックス (j=1,\dots,W) |
| (V_j>0) | 各弾頭が脅かす資産の価値 |
| (p_{ij}\in[0,1]) | インターセプタ (i) が弾頭 (j) を攪乱できる確率（SSPK） |
| (x_{ij}\in{0,1}) | インターセプタ (i) が弾頭 (j) に割り当てられるか否か |
目的関数
全体の期待価値損失を最小化（＝守る資産の期待価値を最大化）：
[ \max \sum_{j=1}^{W} V_j \Bigl( 1-\prod_{i=1}^{I}(1-p_{ij})^{x_{ij}}\Bigr) ]
制約
各インターセプタは最大一つの弾頭にしか割り当てられない（保留可能）：
[ \sum_{j=1}^{W} x_{ij}\le 1,\qquad \forall, i=1,\dots,I . ]
(\prod_{i}(1-p_{ij})^{x_{ij}}) は、割り当てられたすべてのインターセプタが失敗する確率であり、その補数は「少なくとも一台が成功する」確率です。
これに (V_j) を掛けることで、その弾頭を守った場合に期待できる価値損失回避額を得られます。
実際には各ターゲットで (P(\text{track})_j) を乗じた完全モデルもありますが、標準的な WTA では完璧追跡（(P(\text{track})=1)）を仮定します。
複雑性
1986 年に Lloyd と Witsenhausen は、WTA の決定版が NP‑complete であることを示しました[1]。
すなわち、閾値 (T) が与えられたとき、「合計期待価値が ( \ge T )」となる割り当てが存在するか判定する問題は NP‑complete です（最適化版は NP‑hard）。
難しさの根源
線形割り当て問題（例：作業者をタスクに割り当て、コストを最小化）は「各割り当てが他と独立」しており、ハンガリアン法などで多項式時間で解けます。
WTA は目的関数に積の項が含まれるため、あるターゲットに追加インターセプタを割り当てる価値は既に割り当てられた数に依存し、減少報酬 が発生します。
すべての割り当てを相互に考慮せざるを得ないため、分解可能性が失われます。
さらに実務上は 偽装弾（デコイ） の存在も重要です。
Wilkening は分類確率 (P_{ww})（真弾頭として正しく認識される確率）と (P_{dw})（デコイが真弾頭に誤認される確率）を導入し、実効ターゲット数は
[ W^{*}=W\cdot P_{ww}+D\cdot P_{dw} ]
となります。
分類精度が低い場合（(P_{dw}\approx1)）、デコイ全てが弾頭として扱われ、行列の列数 (W) が増大し、計算複雑性はさらに高まります。
実用的な解法
NP‑completeness は「実際に解けない」ことを意味するわけではありません。
Bertsimas と Paskov（2025）は branch‑price‑and‑cut アルゴリズムで、10,000 武器・10,000 ターゲットのインスタンスを 7 分以内に最適解まで到達させる手法を示しました[10]。
1,000 ターゲット・1,500 武器の場合は数秒で解決します。
以前のベンチマークでは 400 台以上の武器で 2 時間タイムアウトが発生していました。
したがって、計算複雑性 はボトルネックではなく、実際には 攻撃者側が問題サイズを自由に増やせる点（弾頭・デコイの数）と 防御側の入力不確実性（SSPK 推定値、追跡確率、ターゲット価値）が主な課題です。
最適解は「防御側の不完全モデルに対して」だけが最適であり、現実世界では常に変動します。
まとめ
- 単一インターセプタ の SSPK は約 56 %（米 GMD）。
- 4 台投入 すると理想化条件下で 96 % の攪乱確率が得られる。
- 実際は 追跡・分類パイプラインの失敗 が大きく、(P(\text{track})) が 0.90 程度だと 4 台でも 86 % 以下に低下。
- WTA は NP‑complete/NP‑hard であり、減少報酬構造が最適化を難しくする。
- デコイの存在は実効ターゲット数を増大させ、計算量を指数的に拡大。
- 最新アルゴリズムでは 10,000×10,000 の規模も秒単位で解決可能だが、攻撃者が問題サイズを増やすことは容易。
- 実際のミサイル防衛は「一方的最適化」ではなく、相手の戦略（弾頭・デコイ配置）と協調した多様な防御パターン を検討する必要がある。
参考文献
-
S. P. Lloyd & H. S. Witsenhausen, “Weapons Allocation is NP‑Complete,” Proceedings of the 1986 Summer Computer Simulation Conference, 1986.
-
R. K. Ahuja et al., “Exact and Heuristic Algorithms for the Weapon‑Target Assignment Problem,” Operations Research, vol. 55, no. 6, pp. 1136–1146, 2007.
-
“Ground‑based Midcourse Defense (GMD),” CSIS Missile Defense Project. https://missilethreat.csis.org/system/gmd/
-
“Golden Dome,” CSIS Missile Defense Project. https://missilethreat.csis.org/system/golden-dome/
-
D. A. Wilkening, “A Simple Model for Calculating Ballistic Missile Defense Effectiveness,” Center for International Security and Cooperation, Stanford University, August 1998.
-
T. Harrison, “Build Your Own Golden Dome: A Framework for Understanding Costs, Choices, and Tradeoffs,” American Enterprise Institute, 2025.
-
“Iranian Attacks on Critical Missile Defense Radars Are a Wake‑Up Call,” The War Zone, 2026. https://www.twz.com/news-features/iranian-attacks-on-critical-missile-defense-radars-are-a-wake-up-call
-
“Iran Hits Key US Radar, Deepening Gulf Missile Defense Woes,” Bloomberg, 2026. https://www.bloomberg.com/news/articles/2026-03-06/iran-hits-key-us-radar-deepening-gulf-missile-defense-woes
-
“Iran Strikes U.S. Military Communication Infrastructure in Mideast,” The New York Times, 2026. https://www.nytimes.com/2026/03/03/world/middleeast/iran-strikes-us-military-communication-infrastructure.html
-
D. Bertsimas & A. Paskov, “Solving Large‑Scale Weapon Target Assignment Problems in Seconds Using Branch‑Price‑and‑Cut,” Naval Research Logistics, vol. 72, pp. 735–749, 2025.
-
“Israeli civilian films double‑team interception,” r/CombatFootage, 2025. https://www.reddit.com/r/CombatFootage/comments/1rrqklj/israeli_civilian_films_doubleteam_interception_of/