Perfect matching problem

Question

Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*m_i$.

I want to find some perfect matching with some given cost. I suspect that this is hard (i.e. NP-complete). Can you solve it quickly? (find an efficient algorithm).

Here is an example: we have three courses, credit hours are 4, 5, 8. Grade points are 4, 3, 2. A solution is a perfect matching between the lists that result in some given GPA.

For this to be computationally meaningful, the largest grade point and largest credit hour are unbounded.

P.S. Yuval hinted the reduction from Subset sum problem. I am interested in hardness proof of strong NP-completeness.

Answer 1

This problem is indeed $NP-complete$ as you have suspected. To see this, we will show a reduction from $SubsetSum$.

The reduction

Let $A,s$ be an instance of $SubsetSum$, where $|A|=n$. We will define $L$ as all the numbers in $A$, in addition to another $n$ zeros. For example, if $A= 4, 5, 8$ then $L=4,5,8,0,0,0$.

Now, we define $M$ to be with $2n$ values, such that we have $n$ ones and $n$ zeros.

The target value will be $s$

Proof

Such a perfect matching defines us a subset $A'\in A$, that $a\in A'$ iff $1$ is matched with $a$. Since we have $n$ values in $A$, and we have $n$ ones and $n$ zeros in $M$, then each pair of $(0,1)$ in $M$ can be assigned to every pair $(a, 0)$ where $a\in A$, and thus any $a\in A$ can be matched with either $0$ or $1$, contributing to the total sum either $a$ or $0$. Therefore, there is a perfect match if and only if there is a subset with that sum (as the value of the matching is a sum of the subset $A'$).