<p>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 (<strong>WTA</strong>) problem is:</p>

<p><strong>Input</strong>: 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}$.
<br><strong>Question</strong>: Does there exist an assignment of the available weapons such that:</p>

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

<p>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$).</p>

<p>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.</p>

<p>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}$:</p>

<ul>
    <li>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}$);</li>
    <li>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}$);</li>
    <li>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})$</li>
</ul>

<p>We set $k = 1$.</p>

<p>($\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}$$</p>

<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:</p>

<p>$$ 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$$</p>

<p>($\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:</p>

<p>$$ D = P \prod_{x \in X'} q_{x,1} + P \prod_{y \in Y'} q_{y,2} \leq 1$$</p>

<p>$W_{\alpha}$ and $W_{\beta}$ cannot both belong to $X'$ (or $Y'$), otherwise:</p>

<p>$$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$$</p>

<p>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>

<p>$$ 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$$</p>

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

<p>Multiplying both sides by the positive quantity $2bz$ we get:</p>

<p>$$ b^2 + z^2 \leq 2bz$$</p>

<p>$$(b - z)^2 \leq 0$$</p>

<p>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>

<p>(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] ):</p>

CC BY-SA 3.0
2013-12-13T23:37:10.623Z
2013-12-14T19:23:54.850Z
2013-12-14T19:23:54.850Z
Marzio De Biasi
<p>Does anybody know a NP-hardness proof of Weapon-target assignment problem (<a href="http://en.wikipedia.org/wiki/Weapon_target_assignment_problem">http://en.wikipedia.org/wiki/Weapon_target_assignment_problem</a>)? 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". </p>

CC BY-SA 3.0
2013-09-20T19:59:02.297Z
If you can't get it any other way, Amazon.com will sell you a copy of the conference proceedings (1986 Summer Conference on Simulation, Reno, NV) for $42. The conference was run by what is now [The Society for Modeling & Simulation International](http://www.scs.org/), who may also be able to help.
David Richerby
CC BY-SA 3.0
2013-09-21T00:41:35.343Z
I've always disliked this problem. We're not working for the army.
Yuval Filmus
CC BY-SA 3.0
2013-09-21T02:45:12.693Z
your local library might retrieve this document for you
Austin Buchanan
CC BY-SA 3.0
2013-09-21T11:47:28.507Z
[this](http://etd.lib.metu.edu.tr/upload/12614452/index.pdf) is a thesis on this topic and briefly described the proof technique of NP-completeness of problem.
Saeed
CC BY-SA 3.0
2013-09-21T12:21:40.363Z
Saeed, I did not find any insight about the proof in the thesis you suggest. Have you any idea where is that in the thesis?
Nicola Gatti
CC BY-SA 3.0
2013-09-23T08:59:51.733Z
@NicolaGatti, in page 12 written:  "static version of the Weapon - Tar-get Allocation problem is an NP-Complete problem by *formulating the problem as a nonlinear integer programming problem*", and I think this point is enough for research or think about it.
Saeed
CC BY-SA 3.0
2013-09-24T01:50:23.363Z
@Saeed: The direction is wrong. One needs to formulate a NP-complete problem as the weapon-target assignment problem.
Yoshio Okamoto
CC BY-SA 3.0
2013-09-24T08:30:24.150Z
@YoshioOkamoto, I think the author of thesis means same thing, usually we do if and only if reductions, otherwise writing this in his/her thesis is nonsense. Also another option for op is to email to the author of thesis and ask him/her to explain this a little bit more, because of lots of options (keywords, key ideas, contacting with author,...) I think this is a good start point.
Saeed
<np-hardness>
Weapon target assignment problem
Nicola Gatti
# Weapon target assignment problem

(Asked by: username_0 on 2013-09-20)

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".

**Tags:** np-hardness

> **Comments:**
> **username_1**: If you can't get it any other way, Amazon.com will sell you a copy of the conference proceedings (1986 Summer Conference on Simulation, Reno, NV) for $42. The conference was run by what is now [The Society for Modeling & Simulation International](http://www.scs.org/), who may also be able to help.  
> **username_2**: I've always disliked this problem. We're not working for the army.  
> **username_3**: your local library might retrieve this document for you  
> **username_4**: [this](http://etd.lib.metu.edu.tr/upload/12614452/index.pdf) is a thesis on this topic and briefly described the proof technique of NP-completeness of problem.  
> **username_0**: username_4, I did not find any insight about the proof in the thesis you suggest. Have you any idea where is that in the thesis?  
> **username_4**: @NicolaGatti, in page 12 written:  "static version of the Weapon - Tar-get Allocation problem is an NP-Complete problem by *formulating the problem as a nonlinear integer programming problem*", and I think this point is enough for research or think about it.  
> **username_5**: @username_4: The direction is wrong. One needs to formulate a NP-complete problem as the weapon-target assignment problem.  
> **username_4**: @YoshioOkamoto, I think the author of thesis means same thing, usually we do if and only if reductions, otherwise writing this in his/her thesis is nonsense. Also another option for op is to email to the author of thesis and ask him/her to explain this a little bit more, because of lots of options (keywords, key ideas, contacting with author,...) I think this is a good start point.  

---

## 1 answers

### Answer by username_6 on 2013-12-13. Score: 3

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 > 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] ):


---

