Missile Defense is NP-Complete | An Optimization Odyssey

The latest conflict in the Middle East has brought missile defense back into
the spotlight. There’s a lot of discussion regarding interceptor stockpiles,
missile stockpiles, and cost. As it turns out, this is a resource allocation
problem. The problem is NP-complete, but that’s far from the reason why missile
defense is a hard problem. To get our bearings, we start with how unreliable a
single interceptor actually is.

SSPK: How good is a single interceptor?

Single Shot Probability of Kill (SSPK) is the probability that an individual
interceptor successfully intercepts one warhead in a single engagement. It
captures sensor accuracy, guidance precision, interceptor quality, etc.
For example, the U.S. Ground-Based Midcourse Defense (GMD) system uses
Ground-Based Interceptors (GBIs) with an estimated SSPK of roughly 56%, based
on the system’s intercept test record [3]. Each GBI costs approximately $75
million, and as of 2024, 44 are deployed across Alaska and California [3].

Improving the Odds: Assign Multiple Interceptors per Warhead

First and foremost, let’s assume that interceptor failures are independent.
That is, one interceptor missing doesn’t affect whether another is able to
achieve a successful hit.

Now, we can compute the probability of at least one interceptor successfully
knocking out an incoming nuclear warhead.

The probability that a single interceptor misses is:

$$P(\text🔥) = 1 – sspk$$

If you fire $n$ interceptors independently, the probability that all of them miss is:

$$P(\text⚡) = (1 – sspk)^🔥$$

Therefore the probability that at least one interceptor kills the target is:

$$P(\text⚡ \mid n \text{ interceptors}) = 1 – (1 – sspk)^{n}$$

Using the publicly available information about the U.S. GMD, we set

$sspk = 0.56$

$$P(\text{kill}) = 1 – (1 – 0.56)^{4} \approx 0.9625 \approx 96\%$$

Note that the independence assumption is optimistic and may not reflect
reality. If interceptor failures are correlated (e.g., all interceptors rely on
the same tracking data and misidentify a decoy as the real warhead), the actual
probability of successful intercept will be lower than what this formula
predicts.

Here’s how the kill probability scales with additional interceptors:

Hence, for one warhead, a defender can launch $4$ interceptors and have a 96%
chance of successfully intercepting the incoming warhead.

Unfortunately, those numbers are optimistic.

$P(\text{track})$: What SSPK Doesn’t Capture

You can’t hit what you can’t see. The formula $P(\text{kill}) = 1 – (1 – sspk)^n$

Wilkening (1998) formalizes this concept with a probability
$P(\text{track})$ that captures the entire
detection-tracking-classification-command&control pipeline [5]. The
comprehensive kill probability becomes:

$$K_w = P(\text{track}) \times \left[1 – (1 – sspk)^n\right]$$

This is a common mode factor. That is, if the target is never detected or is
misclassified as debris, then every interceptor assigned to it fails. The
independence assumption from the previous section is conditional upon
successful tracking.

Here’s what the kill probability table looks like when $P(\text{track}) < 1$

At $P(\text{track}) = 0.90$

Wilkening’s analysis shows that for national missile defense to achieve 80%
confidence of destroying all warheads against even modest attacks (4–20 reentry
vehicles), you need $P(\text{track}) > 0.978$

Hence, the probabilities of successful interception in the previous section are
best case. The effective kill probability in the real world is always
lower, because $P(\text{track})$ is always less than 1.

And $P(\text{track})$ is not just passively less than $1$ — an adversary will
actively try to drive it toward zero. Recent events have demonstrated this
directly. Namely, missile defense radars have been successfully targeted and
destroyed in the (as of today’s date) active conflict, eliminating tracking
coverage for entire regions [7][8][9]. These sensors cost hundreds of
millions to billions of dollars each. Destroying or degrading them doesn’t just
reduce $P(\text{track})$ — it can eliminate it entirely for the coverage area
those radars served. No amount of interceptors can compensate for a tracking
pipeline that no longer exists.

This tracking issue also comes up in one of the more pernicious software
bugs of all time — the 1991
Patriot missile failure. A cumulative fixed-point truncation error in the
system’s clock caused the tracking radar to look in the wrong part of the sky,
and the incoming Scud missile was never tracked. Twenty-eight servicemembers
were killed. The interceptors were physically capable, but $P(\text{track})$
was effectively zero.

For now, let’s assume we have great tracking. What happens when the adversary
fires more than one missile?

Multiple Incoming Missiles

You have $I = 7$

The “right” allocation depends on the relative values of the targets.

Now let’s scale this up. Assume an inventory of $44$ interceptors and $15$
incoming warheads. Each warhead is aimed at a different city, each with
different estimated values, and each interceptor has a different SSPK against
each warhead — depending on geometry, timing, and type of interceptor. Then,
the number of possible assignments explodes combinatorially.

The Weapon-Target Assignment Problem

The allocation problem above has a formal name: the Weapon-Target Assignment
(WTA) problem.

Given:

$I$ interceptors (weapons), indexed $i = 1, \ldots, I$

$W$ warheads (targets), indexed $j = 1, \ldots, W$

A value $V_j > 0$

An SSPK matrix $p_{ij} \in [0, 1]$

Decision variables $x_{ij} \in \{0, 1\}$

The objective is to maximize the total expected value of successfully defended assets:

$$\max \sum_{j=1}^{W} V_j \left(1 – \prod_{i=1}^{I} (1 – p_{ij})^{x_{ij}}\right)$$

subject to each interceptor being assigned to at most one warhead:

$$\sum_{j=1}^{W} x_{ij} \leq 1, \quad \forall \, i = 1, \ldots, I$$

(Using $\leq 1$

In essence, for each warhead, the product $\prod_{i=1}^{I}(1 – p_{ij})^{x_{ij}}$

Note that a more complete model would multiply each term by $P(\text{track})_j$

In 1986, Lloyd and Witsenhausen proved that the decision version of the WTA
problem is NP-complete via reduction from 3-Dimensional Matching [1]. That is,
given a threshold $T$, determining whether there exists a feasible assignment
with total expected value saved $\geq T$

Why is this hard? In a linear assignment problem (e.g., assign workers to tasks
to minimize total cost), the value of each assignment is independent of every
other — the cost of assigning worker $i$ to task $j$ doesn’t change based on
other assignments. Despite having $n!$ feasible solutions, this structure
allows polynomial-time algorithms such as the Hungarian algorithm. WTA breaks
this property. The product terms in the objective mean that the marginal value
of assigning an additional interceptor to a target depends on how many are
already assigned there — there are diminishing returns. This couples all
assignments together: you cannot evaluate one assignment without knowing the
rest. This nonlinearity destroys the decomposition properties that make the
linear assignment problem tractable.

And $W$ is likely larger than the number of real warheads. A single warhead can
deploy many decoys that are difficult to distinguish from real reentry vehicles
in the midcourse phase. Wilkening formalizes this with classification
probabilities: let $P_{ww}$

$$W^* = W \cdot P_{ww} + D \cdot P_{dw}$$

where $D$ is the number of decoys. If discrimination is poor ($P_{dw}$

NP-completeness does not mean practically unsolvable. Bertsimas and Paskov
(2025) developed a branch-price-and-cut algorithm that solves instances with
10,000 weapons and 10,000 targets to provable optimality in under 7 minutes on
a Macbook Pro [10]. Instances with 1,000 targets and 1,500 weapons solve in seconds.
The prior state-of-the-art timed out at 2 hours for problems with more than 400
weapons. The computational complexity is not the bottleneck. The bottleneck is
that the attacker chooses the problem size — adding a warhead or decoy is
cheap, and each one adds another column to the SSPK matrix. Even with an
oracle that solves WTA instantly, the defender’s inputs, (i.e., SSPK estimates,
tracking probabilities, target values), are uncertain. The “optimal” solution
is optimal only with respect to the defender’s imperfect model of the attack.

Discussion

To recap, let’s plug in the real numbers once more. If you need 4 interceptors
per warhead for a 96% chance of interception, then 44 GBIs provide reliable
defense against at most $\frac{44}{4} = 11$

Directed energy has been proposed as a cost-effective alternative, but
introduces its own scheduling constraints — dwell time, platform coverage,
atmospheric degradation — with similar scaling issues [4][6].

Finally, it’s important to note this analysis above treats missile defense as a
one-sided optimization. In reality, just as the defender solves WTA to maximize
expected survival, the attacker solves their own allocation problem —
distributing warheads and decoys across targets to minimize the defender’s
expected survival. The attacker has structural advantages: they choose the
problem size (how many warheads and decoys to deploy), they can observe the
defense architecture before committing, and they have the first mover
advantage. The defender must prepare for a range of possible attacks; however,
the attacker only needs to optimize against the defense that exists.

References

1. S. P. Lloyd and H. S. Witsenhausen, “Weapons Allocation is NP-Complete,” Proceedings of the 1986 Summer Computer Simulation Conference, 1986.
2. R. K. Ahuja, A. Kumar, K. C. Jha, and J. B. Orlin, “Exact and Heuristic Algorithms for the Weapon-Target Assignment Problem,” Operations Research, vol. 55, no. 6, pp. 1136–1146, 2007.
3. “Ground-based Midcourse Defense (GMD),” CSIS Missile Defense Project. https://missilethreat.csis.org/system/gmd/
4. “Golden Dome,” CSIS Missile Defense Project. https://missilethreat.csis.org/system/golden-dome/
5. D. A. Wilkening, “A Simple Model for Calculating Ballistic Missile Defense Effectiveness,” Center for International Security and Cooperation, Stanford University, August 1998.
6. T. Harrison, “Build Your Own Golden Dome: A Framework for Understanding Costs, Choices, and Tradeoffs,” American Enterprise Institute, 2025.
7. “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
8. “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
9. “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-in-mideast.html
10. D. Bertsimas and 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.
11. “Israeli civilian films double-team interception,” r/CombatFootage, 2025. https://www.reddit.com/r/CombatFootage/comments/1rrqklj/israeli_civilian_films_doubleteam_interception_of/