# Proving NP-Complete problem by reduction of subset-sum

My assignment question as "given a multiset of symbols (letters) L from an alphabet Σ (thus, the same letter may appear in L multiple times), and a set of words W ⊆ Σ' , UseAllLetters asks if it is possible to use all letters from L to make words belonging to W. You may form the same word multiple times. Prove that UseAllLetters is NP-complete."

I'm new learning NP problems and still having trouble to understand the intuition behind this. But I'll try my best and sharing my idea here to verify that I'm on the right track.

My suggestion as following:

To prove this question is NP-complete, we can do reduction to subset-sum problem, but we also have to show few things.

1.This problem is in NP. (I'm stuck on this)

2.Any NP-complete problem Y can be reduced to X.

So we choose subset-sum problem, as it defined as:Given a set X of integers and a target number t, find a subset Y ⊆ X such that the member of Y add up to exactly t. Which is similar to our problem, we can find a subset of letters $$l$$ in our L that make words belonging to W if we are able to find a subset Y ⊆ X such that the member of Y add up to t.

1. The reduction works in polynomial time.

2. UseAllLetters problem has solution iff subset-sum has solution. I'm also stuck on this, it seems like I have to argue the correctness of my reduction, and I'm not sure my reduction is the right way to do it, I just do like one-to-one mapping to subset-sum problem.

Any feedback?

To prove NP-hardness, I suggest a reduction from the Exact-Cover problem instead, since it is more related. In the exact cover problem, you are given a Universe of elements $$\mathcal{U}$$ and a family of sets $$\mathcal{F} = \{F_1, \dots F_n\}$$ over the universe (A set of subsets of the universe). The output is whether there is a subset of the sets in the family that cover the whole universe and each element is covered exactly once (included in exactly one chosen set). A reduction to your problem would be as follows. We set $$\Sigma = W = \mathcal{U}$$ (each element in $$W$$ is repeated exactly once). From each set $$F \in \mathcal{F}$$ we build a word $$s$$ that contains exactly the elements in the set (in any order).
If the instance of the exact-cover problem is a yes-instance, then there is a subset of the family $$\{F_{i_1}, \dots F_{i_k}\}$$ that covers each element in the universe exactly ones. The words $$s_{i_1}, \dots s_{i_k}$$ we built from these sets cover each element in $$W$$ exactly once so it is also a yes instance. On the other hand, if the instance of your problem is a yes instance, there is a ste of words $$s_{i_1}, \dots s_{i_k}$$ that covers each element in $$W$$ and hence in $$\Sigma$$ exactly once. The sets $$F_{i_1} \dots F_{i_k}$$ we build the words from cover each element in the universe exactly once.