Well if it isnt the the halting problem exactly i suspect its damn near as hard. How about these two:

/aaaa(bc|bd|be|(b|b)(a(a(a(a)))|baba|aaaa)/
/aaaab?aaaa/
[download]

I suspects its a lot easier to show that regex E can produce something that regex R wont accept, but saying for sure that R will accept all patterns producable by E isnt so easy. And IMO neither are approachable problems at all. Id be thinking of alternate solutions. One possibility is to produce something that generates random data from the E pattern and then hammer the R pattern with the products to see but obviously this wont be a proof, just a strong argument.

/me wonders if he still has his data from regex code...