Proving NP-Complete problem by reduction of subset-sum

Question

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.

3. The reduction works in polynomial time.

4. 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?

Answer 1

To prove a problem is NP-complete you have to prove it is in NP and that it is NP-hard. NP-hardness proof is usually however, a reduction from one NP-hard problem. To prove that the problem is NP, you can either describe a non-deterministic polynomial time algorithm for the problem (An NTM that decides the language of the yes-Instances in polynomial time), or you can show that there is a certificate of polynomial size for each yes-instance, such that given the instance with the certificate you can in polynomial time prove that the instance is a yes instance.

Both ways are quite easy here. A polynomial certificate would be an answer of the problem. You can verify if a given set of words as a solution really uses each letter exactly once. Describing an NTM is also straightforward, where the NTM guesses all possible subsets of words and checks for each subset if it covers all letters and each letter exactly once.

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.