Weapon target assignment problem Does anybody know a NP-hardness proof of Weapon-target assignment problem (http://en.wikipedia.org/wiki/Weapon_target_assignment_problem)? Lloyd and Witsenhausen produced a reduction from 3-EXACT-COVER, but it seems that there is no chance to get their paper titled "Weapons allocation is NP-complete".
I don't have access to the original paper, but this is an alternate reduction from SUBSET PRODUCT. The decision version of the WEAPON TARGET ASSIGNMENT (WTA) problem is:

Input: Given an integer $k$, $W_i$ weapons of type $i = 1,...,m$, $n$ targets $j=1,...,n$ having values $V_j$; each weapon type has a certain probability of destroying each target, given by $p_{i,j}$.
Question: Does there exist an assignment of the available weapons such that:

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

where $x_{i,j} = 1$  if weapon $i$ is assigned to target $j$ ($x_{i,j} = 0$ otherwise), and $q_{i,j} = 1 - p_{i,j}$ (survival probability of target $j$ when hit by weapon $i$).

Given a set of positive integers $A= \{a_1, a_2, ..., a_m\}$, and a target product $b$; the SUBSET PRODUCT problems asks for a subset $X \subseteq \{1,2,...,m\}$ such that $\prod_{i \in X} a_i = b$. Let $P = \prod 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 &gt; 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.

(P.S. Unfortunately, despite the 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] ):