Missile Defense Is NP-Complete

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: $1 - SSPK$. If you fire $n$ interceptors independently, the probability that all of them miss is: $(1 - SSPK)^n$. Therefore the probability that at least one interceptor kills the target is: $P_k = 1 - (1 - SSPK)^n$.

Using the publicly available information about the U.S. GMD, we set $SSPK = 0.56$ and $n = 4$, which gives us $P_k = 1 - (1 - 0.56)^4 = 1 - (0.44)^4 \approx 0.9625$.

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:

| Interceptors (n) | $P_k$ | |---|---| | 1 | 56.00% | | 2 | 80.64% | | 3 | 91.48% | | 4 | 96.25% | | 5 | 98.35% |

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_t$: What SSPK Doesn’t Capture

You can’t hit what you can’t see. The formula assumes you’ve already successfully detected the incoming warhead, tracked it with enough precision to commit an interceptor, correctly classified it as a real warhead (i.e., not a decoy), and that your command & control systems are functional. In reality, all of these steps can fail. In that case, it doesn’t matter how many more interceptors you are willing to expend.

Wilkening (1998) formalizes this concept with a probability $P_t$ that captures the entire detection-tracking-classification-command&control pipeline [5]. The comprehensive kill probability becomes: $P_{kill} = P_t \times [1 - (1 - SSPK)^n]$. 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_t$ varies:

| Interceptors (n) | $P_t = 1.0$ | $P_t = 0.95$ | $P_t = 0.90$ | |---|---|---|---| | 1 | 56.00% | 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% |

At $P_t = 0.9$, the “96% kill probability” with 4 interceptors drops to under 87%. Even an allocation of 5 interceptors reaches only 89%, still short of what the idealized model achieves with just 3.

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_t > 0.99$. Below that threshold, no amount of SSPK improvement is sufficient. This is an extraordinarily high bar — the entire pipeline (i.e., detection, tracking, classification, etc.) must work nearly perfectly, nearly every time.

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_t$ is always less than 1. And $P_t$ 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 active conflicts, eliminating tracking coverage for entire regions. These sensors cost hundreds of millions to billions of dollars each. Destroying or degrading them doesn’t just reduce $P_t$ — 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_t$ was effectively zero.

Multiple Incoming Missiles

You have $W$ interceptors and $T$ incoming warheads. The warheads have different targets: warhead 1 is headed for a major city, warhead 2 for an airport, and warhead 3 for a military base. How should you allocate your interceptors? The “right” allocation depends on the relative values of the targets. Now let’s scale this up. Assume an inventory of $W$ interceptors and $T$ 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 $W$ interceptors, $T$ warheads, a value $V_j$ for each warhead, and an SSPK matrix $P_{ij}$, the objective is to maximize the total expected value of successfully defended assets: $\max \sum_{j=1}^{T} V_j (1 - \prod_{i=1}^{W} (1 - P_{ij})^{x_{ij}})$.

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