Missile Defense is NP-Complete

摘要

深度分析导弹防御中的资源分配问题，证明武器-目标分配（WTA）问题是NP-Complete的。

背景知识

SSPK - 单发杀伤概率

美国GBI拦截弹的SSPK约为56%，每枚造价约7500万美元。

P(track) - 跟踪概率

包括检测、跟踪、分类、指挥控制全流程的成功概率。即使跟踪失败，拦截器再多也无用。

武器-目标分配问题 (WTA)

给定：

• I个拦截器
• W个来袭弹头
• 每个弹头的价值Vj
• 拦截器i击落弹头j的概率 pij

目标：最大化成功防御的预期总价值。

为什么困难？

线性分配问题的边际价值是独立的，但WTA中向一个目标分配额外拦截器的边际价值取决于已分配的数量——这种非线性将所有分配耦合在一起。

实践解法

NP-Complete并不意味着实际不可解。Bertsimas和Paskov (2025)开发了一种分支-定价-切割算法，可在7分钟内解决10,000×10,000规模的问题。