Exploring the Weapon-Target Assignment problem: how missile defense connects to NP-completeness, SSPK probability calculations, and how saturation attacks exploit computational limits.

Hacker News is a community-driven platform for sharing and discussing technology news, startups, and programming-related topics. Through user submissions and comments, Hacker News offers insights into emerging technology trends, industry developments, and entrepreneurial ventures. Readers can participate in discussions, share their insights, and stay informed about the latest advancements in technology and innovation.

Hacker News

The Weapon-Target Assignment (WTA) problem — how to optimally allocate missile interceptors against incoming warheads — is formally NP-complete, proven via reduction from 3-Dimensional Matching. The post walks through Single Shot Probability of Kill (SSPK) math, the Wilkening detection-tracking-classification factor that further degrades real-world intercept probability, and how decoys inflate the problem size. Despite recent algorithmic advances (Bertsimas & Paskov 2025 solving 10,000×10,000 instances in under 7 minutes), computational complexity is not the real bottleneck. The attacker controls problem size cheaply, tracking pipelines can be destroyed or degraded, and the defender must optimize under deep uncertainty. Real numbers show the current 44 U.S. GBIs provide reliable defense against only ~11 ICBMs, and a barrage of 10 warheads plus 10 decoys demands 73 interceptors.

Missile Defense is NP-Complete

Improving the Odds: Assign Multiple Interceptors per Warhead

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