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.
The reduction works in polynomial time.
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.