Missile Defense Is NP-Complete

Context

미사일 방어 시스템은 표면적으로 단일 요격체의 성공 확률(SSPK 56%)을 여러 요격체로 보강하는 단순 확률 문제로 보이지만, 실제로는 탐지-추적-분류-지휘통제 파이프라인 전체가 작동해야만 효과를 발휘한다. 이상적 모델에서 4개 요격체로 96% 성공 확률을 예측하지만, 실제 추적 성공 확률 P(track) = 0.90일 때는 87% 미만으로 급격히 하락한다.

Technical Solution

• SSPK 기반 확률 모델 도입: 단일 요격체 56% 성공률을 기반으로 n개 요격체 할당 시 kill 확률을 P(kill|n) = 1 - (1 - sspk)^n 공식으로 계산
• 추적 성공 확률 P(track) 팩터 통합: Wilkening(1998) 방식으로 탐지-추적-분류-C2 전체 파이프라인을 K_w = P(track) × [1 - (1 - sspk)^n]로 재구성하여 공통 장애 모드 반영
• 요격체 할당량 증대 전략: 이상적 조건에서 1개→4개 요격체 할당 시 56%→96.25% 성공 확률 달성, 추적 성공률 0.90 조건에서는 동일 목표 달성을 위해 5개 필요
• 파이프라인 신뢰도 임계값 설정: P(track) > 0.978 이상 유지 필요(4~20개 재진입체 공격에 80% 신뢰도 달성)
• 자원 할당 문제의 NP-완전성 확인: 공격 측은 기존 방어만 최적화하면 되는 비대칭적 이점 보유

Impact

P(track) = 0.95 조건에서 4개 요격체로 91.44% 성공 확률 달성 (이상 모델 대비 4.81% 감소), P(track) = 0.90 조건에서는 86.63% (9.62% 감소).

Key Takeaway

방어 시스템의 실효성은 개별 요소의 확률보다 탐지-추적-분류-통제 전체 파이프라인의 신뢰도에 의해 결정되며, 불완전한 파이프라인은 추가 자원 투입으로도 보완 불가능한 구조를 갖는다.