As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation problem) is the puzzle of defining the shortest possible regular expression that accepts every word in set A and no word in set B. Norvig's post includes an algorithm for generating a reasonably short candidate, and he notes that his approach involves solving an NP-complete Set Cover problem, but he's also careful to point out that his approach doesn't consider every possible regular expression, and of course his isn't necessarily the only algorithm, so his solutions aren't guaranteed to be optimal, and it's also possible that some other assuredly polynomial-time algorithm could find equivalent or better solutions.
For concreteness' sake and to avoid having to solve the optimization question, I think the most natural formulation of Regular Expression Separation would be:
Given two (finite) sets $A$ and $B$ of strings over some alphabet $\Sigma$, is there a regular expression of length $\leq k$ that accepts every string in $A$ and rejects every string in $B$?
Is anything known about the complexity of this particular separation problem? (Note that since I've specified $A$ and $B$ as finite sets of strings, the natural notion of size for the problem is the total lengths of all strings in $A$ and $B$; this swamps any contribution from $k$). It seems highly likely to me that it is NP-complete (and in fact, I would expect the reduction to be to some sort of cover problem) but a few searches haven't turned up anything particularly useful.