I asked the problem for regular expression(the theoretical kind) for a finite set on cstheory a while ago.

http://cstheory.stackexchange.com/questions/16860/minimizing...

Apparently this problem is still open.