NP-Complete Reality — Extra Small

A paper hit Hacker News today that connects an abstract CS result to a very concrete problem: why it’s nearly impossible to optimally defend against ballistic missile attacks.

The short version: the Weapon-Target Assignment (WTA) problem is NP-complete. But the mathematical hardness isn’t actually why missile defense is difficult.

The harder problem is that your adversary controls the input.

The Probability Math

Start with a single interceptor. The U.S. Ground-Based Midcourse Defense system has Ground-Based Interceptors (GBIs) with an estimated kill probability of about 56% per engagement — “SSPK” in the jargon. Each GBI costs $75 million. The U.S. has 44 deployed.

If you fire two independent interceptors at the same warhead, the probability that both miss is (1 - 0.56)² = 0.44² ≈ 19%. So the probability that at least one hits is ~81%. Four interceptors gets you 96%.

This sounds manageable until you realize: 44 GBIs ÷ 4 per warhead = you can cover 11 warheads reliably.

But those are the idealized numbers. The real kill probability is lower, because everything depends on whether the tracking system worked first. Wilkening’s more complete model introduces a pipeline factor ψ — the probability that the entire detection-tracking-classification-command chain functioned correctly. If ψ = 0.95, your 96% becomes 91%. If ψ = 0.90, it drops to 87%.

And ψ isn’t static. An adversary can target the radar systems. Iran has demonstrated this in 2026: attacking the radar infrastructure directly drives ψ toward zero. No amount of interceptors can compensate for a destroyed tracking pipeline.

Why WTA Is NP-Hard

Now scale up. You have N interceptors, M incoming warheads, each targeting a different asset (city, base, infrastructure), each with different values. Each interceptor has different kill probability against each warhead depending on geometry and timing.

The question: which interceptors do you assign to which warheads to maximize total expected value of defended assets?

This is the Weapon-Target Assignment problem. Lloyd and Witsenhausen proved in 1986 that the decision version is NP-complete.

The reason is a property called nonlinearity in the objective. In a standard linear assignment problem (assign N workers to N tasks), each assignment has a fixed cost independent of others — you can decompose and solve in polynomial time. WTA breaks this.

The marginal value of assigning an additional interceptor to a warhead depends on how many are already assigned there. Going from 0 to 1 interceptors dramatically increases kill probability. Going from 4 to 5 interceptors barely changes it (from 96% to 98%). The objective has a multiplicative structure that couples every assignment to every other.

You cannot evaluate one assignment without knowing the rest. The decomposition trick doesn’t work. The problem is NP-complete.

But That’s Not the Bottleneck

Here’s the counterintuitive part: recent work by Bertsimas and Paskov (2025) showed that instances with 10,000 weapons and 10,000 targets can be solved to provable optimality in under 7 minutes on a MacBook Pro.

Computational complexity doesn’t mean practical impossibility. NP-complete problems can have efficient exact solvers for practically-sized instances. The mathematics just says that worst-case instances require exponential time — but real-world instances often don’t look like worst-case.

The actual bottleneck is asymmetric: the attacker chooses the problem size.

Adding one warhead is cheap. Adding one decoy is cheap. Each addition:

Adds another column to the kill-probability matrix
Increases M, the number of targets
Makes the optimization harder
Consumes more of the finite interceptor inventory

And decoys are the multiplier that breaks the math. Wilkening’s model shows that 10 warheads accompanied by 10 decoys requires 73 interceptors to defend — not because of computation, but because you can’t tell which are real without spending interceptors on everything.

With poor discrimination (decoys that look like warheads), every decoy is another target in the WTA formulation. An attacker with 10 warheads and 30 decoys forces the defender to solve a 40-target problem, consuming interceptors on targets that don’t matter.

The Adversarial Asymmetry

This is where the problem becomes genuinely hard in a different sense — game-theoretic, not computational.

The defender must prepare for a range of possible attacks. They don’t know how many warheads are coming, which decoys are real, or which assets the attacker prioritizes. They must solve WTA under deep uncertainty about the input parameters.

The attacker faces none of this. They observe the defense architecture before committing. They know (roughly) how many interceptors exist and where they’re deployed. They can choose an attack that optimizes against the specific defense that exists.

This is structural: the defender solves a minimax problem (minimize the maximum damage under any attack), while the attacker solves a simpler optimization (maximize damage against a known defense). The defender’s problem is strictly harder.

Concretely: with 44 GBIs and 4 interceptors per warhead, the U.S. can reliably cover 11 targets. A sophisticated adversary can fire 12. Even a constrained attack saturates the defense.

What This Means for AI-Adversarial Systems

There’s a broader lesson here beyond missile defense: any optimization problem under adversarial conditions has a different character than optimization under fixed constraints.

The clean CS complexity result — WTA is NP-complete — is interesting but doesn’t capture the actual difficulty. The actual difficulty is that:

The attacker controls the problem parameters (adversarial input)
The defender must solve under uncertainty (incomplete information)
The cost asymmetry favors offense (adding warheads/decoys is cheaper than adding interceptors)

This maps almost exactly to how security researchers think about adversarial ML, red-teaming, and jailbreak resistance. A model that performs well against all known attacks might still be brittle against a novel attack designed specifically for it. The attacker doesn’t need to solve the general problem — just the specific one.

The Weapon-Target Assignment problem is NP-complete.

But the reason missile defense is difficult is that your adversary picked the input.

Based on the analysis by Saveliy Yusufov (smu160.github.io, March 2026) and Wilkening (1998).