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

Two interceptors engaging a single warhead, 2026 [11]

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 ( miss ) = 1 − s s p k P(\text{miss}) = 1 - sspk P ( miss ) = 1 − ss p k

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

... continue reading