The decision version of the Weapon-Target Assignment (WTA) problem is as follows:

There are a number of weapons and a number of targets. The weapons are of type $i = 1, \ldots, m$ . There are $W_{i}$ available weapons of type $i$. Similarly, there are $j = 1, \ldots, n$ targets, each with a value of $V_{j}$ . Any of the weapons can be assigned to any target. Each weapon type has a certain probability of destroying each target, given by $p_{i,j}$ . Does there exist a weapon-target assignment such that:

$$D = \sum_{j=1}^n V_j \prod_{i=1}^m q_{i,j}^{x_{i,j}} \leq k$$

where $k$ is a given integer; $x_{i,j} = 1$ if weapon $i$ is assigned to target $j$, $x_{i,j} =0$ otherwise; $q_{i,j} = 1 – p_{i,j}$ is the survival probability of target $j$ when hit by weapon $i$. No more than $W_i$ weapons of type $i$ can be used, so we must add the following constraint:

$$\sum_{j=1}^n x_{i,j} \leq W_i \quad \mbox{ for } i = 1,\ldots,m$$

WTA problem is NP complete (see L. Chen, C. J. Ren, and S. Deng, “An efficient approximation for weapon-target assignment,” vol. 1, Computing, Communication, Control, and Management. ISES International Colloquium, 2008, pp. 764-767), we give an alternate hardness proof using a reduction from the NP-complete SUBSET PRODUCT problem.

Theorem 1: WTA problem is NP-hard.

Proof: Given a set of positive integers $A= \{a_1, a_2, …, a_m\}$, and a target product $b$; the NP-complete  SUBSET PRODUCT problem asks for a subset $X \subseteq \{1,2,…,m\}$ such that $\prod_{x \in X} a_x = b$. Let $P = \prod_{i=1}^m a_i$, note that if $b \nmid P$ then the subset product problem doesn’t have a solution.

We can build a WTA instance with two targets ($n=2$) having the same value $V_1 = V_2= P$ and $m+2$ weapons $W_1,W_2,…,W_m,W_{\alpha},W_{\beta}$:

• weapons $W_1,W_2,…,W_m$ can destroy both targets with probability $p_{i,1} = p_{i,2} = 1 – \frac{1}{a_i}$ (the survival probability is $q_{i,1} = q_{i,2} = \frac{1}{a_i}$);
• weapon $W_{\alpha}$ can destroy both targets with probability $p_{i,1} = p_{i,2} = 1 – \frac{b}{2P}$ (the survival probability is $q_{i,1} = q_{i,2} = \frac{b}{2P}$);
• weapon $W_{\beta}$ can destroy both targets with probability $p_{i,1} = p_{i,2} = 1 – \frac{1}{2b}$ (the survival probability is $q_{i,1} = q_{i,2} = \frac{1}{2b})$

We set $k = 1$.

($\Rightarrow$) Suppose that the original subset sum problem has a solution $X$; let $Y=\{1,\ldots,m\} \setminus X$.
Then
$$\prod_{i \in X} \frac{1}{a_i}=\frac{1}{b},\quad \prod_{y \in Y} \frac{1}{a_y} = \frac{b}{P}$$

If we assign weapons $W_x, x \in X$ and $W_{\alpha}$ to target 1; weapons $W_y, y \in Y$ and $W_{\beta}$ to target 2 we get:

$$ D= V_1 * \frac{b}{2P}* \frac{1}{b}  + V_2 * \frac{1}{2b}* \frac{b}{P} = P * \frac{b}{2P}* \frac{1}{b}  + P * \frac{1}{2b}* \frac{b}{P}  = 1$$

($\Leftarrow$) Suppose that the WTA instance has a solution and let $X’,Y’$ be the indices of the weapons assigned to target 1 and 2 respectively ($X’,Y’\subseteq \{1,\ldots,m,\alpha,\beta\}$). We must have:

$$ D = P \prod_{x \in X’} q_{x,1} + P \prod_{y \in Y’} q_{y,2} \leq 1$$

$W_{\alpha}$ and $W_{\beta}$ cannot both belong to $X’$ (or $Y’$), otherwise:
$$P \frac{1}{2b}*\frac{b}{2P}*\frac{1}{ \prod_{x \in X’\setminus \{\alpha,\beta\}} a_x} + \frac{P}{ \prod_{y \in Y’} a_y} \geq \frac{1}{4 \prod_{x \in X’\setminus \{\alpha,\beta\}} a_x}+1 > 1$$

So suppose that weapon $W_{\alpha}$ is assigned to target 1 and $W_{\beta}$ to target 2; let $X = X’ \setminus \{ \alpha \}, Y = Y’ \setminus \{ \beta \}$; we must have:

$$ P \frac{b}{2P} \prod_{x \in X} \frac{1}{a_x} + P\frac{1}{2b} \prod_{y \in Y} \frac{1}{a_y} \leq 1$$

$$\mbox{if } z = \prod_{x \in X} a_x, \quad \frac{b}{2z} + \frac{z}{2b} \leq 1$$

Multiplying both sides by the positive quantity $2bz$ we get:

$$ b^2 + z^2 \leq 2bz$$

$$(b – z)^2 \leq 0$$

So we must have $b = z = \prod_{x \in X} a_x$, so $X$ is a valid solution for the original SUBSET PRODUCT problem.

$\Box$

It is easy to see that a solution to the WTA problem can be verified in polynomial time, so we can conclude:

Theorem 2: WTA problem is NP-complete.

(P.S. Unfortunately, despite the (NP-) hardness of this problem, the war between peoples seems to be a lot easier to start …”The day the power of love overrules the love of power, the world will know peace.” [Mahatma Gandhi] ):