<p>This problem is in NP. (easy to verify a given solution)</p>

<p>Subset sum is NP-Complete, so this problem can be reduced to subset sum.</p>

CC BY-SA 4.0
2019-07-17T17:43:54.767Z
Can we really say that there will be a solution =T ?
AVIK DUTTA
CC BY-SA 4.0
2019-07-17T09:46:20.247Z
2019-07-17T09:46:20.247Z
hqztrue
<p>Let there be <span class="math-container">$n$</span> set of ordered pairs<br>
<span class="math-container">$s_1=\{(c_1,f_1),(c_1,f_2) ...(c_1,f_m)\}$</span>,<br>
<span class="math-container">$s_2=\{(c_2,f_1),(c_2,f_2) ...(c_2,f_m)\}$</span>,<br>
<span class="math-container">$s_3=\{(c_3,f_1),(c_3,f_2) ...(c_3,f_m)\}$</span>,<br>
....<br>
<span class="math-container">$s_n=\{(c_n,f_1)(c_n,f_2) ...(c_n,f_m)\}$</span></p>

<p>and</p>

<p><span class="math-container">$T((c,f))$</span> be a function that takes an ordered pair or element of the sets and returns a positive rational number.</p>

<p>can we select one element each from all the <span class="math-container">$n$</span> sets such that <span class="math-container">$\sum T((c_i,f_j)) =T$</span> where <span class="math-container">$\bigcap_{i=1}^{n } c_i =\phi$</span></p>

CC BY-SA 4.0
2019-07-16T16:31:37.523Z
I think that the question tries to be that we need to select a transversal, i.e., at most one element from each column. Am I right?
domotorp
CC BY-SA 4.0
2019-07-16T16:35:36.067Z
@domotorp yes that would be one way to put it
AVIK DUTTA
CC BY-SA 4.0
2019-07-16T19:57:52.193Z
Well, I really don't think this question belongs here, it does look too easy.
domotorp
<np-hardness><subset-sum>
Can we map this problem to subset-sum?
AVIK DUTTA
# Can we map this problem to subset-sum?

(Asked by: username_0 on 2019-07-07)

Let there be $n$ set of ordered pairs  
$s\_1=\{(c\_1,f\_1),(c\_1,f\_2) ...(c\_1,f\_m)\}$,  
$s\_2=\{(c\_2,f\_1),(c\_2,f\_2) ...(c\_2,f\_m)\}$,  
$s\_3=\{(c\_3,f\_1),(c\_3,f\_2) ...(c\_3,f\_m)\}$,  
....  
$s\_n=\{(c\_n,f\_1)(c\_n,f\_2) ...(c\_n,f\_m)\}$

and

$T((c,f))$ be a function that takes an ordered pair or element of the sets and returns a positive rational number.

can we select one element each from all the $n$ sets such that $\sum T((c\_i,f\_j)) =T$ where $\bigcap\_{i=1}^{n } c\_i =\phi$

**Tags:** np-hardness, subset-sum
> **Comments:**
> **username_1**: I think that the question tries to be that we need to select a transversal, i.e., at most one element from each column. Am I right?  
> **username_0**: @domotorp yes that would be one way to put it  
> **username_1**: Well, I really don't think this question belongs here, it does look too easy.  

---

## 1 answers

### Answer by username_2 on 2019-07-17. Score: 0

This problem is in NP. (easy to verify a given solution)

Subset sum is NP-Complete, so this problem can be reduced to subset sum.

> **Comments:**
> **username_0**: Can we really say that there will be a solution =T ?  

---

