tilly,
Have you read How many words does it take? According to blokhead, this is the minimum set cover problem. Of course, I didn't have a universe of letters - I just had the standard english alphabet. It was fun. Of course, if I were doing it over again today, I would do it differently.
I had read it, but it had slipped my mind. And yes, that is a very good example of a problem being feasible despite looking like it was NP-complete. And I like Re: How many words does it take?'s comment that when we think we're faced with an NP-complete problem, we are probably trying to solve the wrong problem.