Here's an interesting development.

A related problem which is PSPACE-complete is the problem: Given a regex R, is there any string that R will not match? Now, it's not known for sure that PSPACE-complete problems are intractible, although it's very likely. (And in particular, PSPACE-complete problems are at least as hard as NP-complete problems.) But here's the interesting part. Normally, in computer science, regex notations only include literal symbols, concatenation, |, *, and parenthese for grouping. If you extend thge regex notation to allow {2} as well, the problem becomes provably intractible and can be shown to require an exponential amount of space.