Missile Defense Is NP-Complete

Summary

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−sspkP(\text{miss}) = 1 - sspkP(miss)=1−sspk If you fire nnn interceptors independently, the probability that all of them miss is: P(all miss)=(1−sspk)nP(\text{all miss}) = (1 - sspk)^{n}P(all miss)=(1−sspk)n Therefore the probability that at least one interceptor kills the target is: P(kill∣n interceptors)=1−(1−sspk)nP(\text{kill} \mid n \text{ interceptors}) = 1 - (1 - sspk)^{n}P(kill∣n interceptors)=1−(1−sspk)n Using the publicly available information about the U.S. GMD, we set sspk=0.56sspk = 0.56sspk=0.56 and n=4n = 4n=4, which gi...