Comment by gohrt

For a given piece of text, pattern-matching is (if P!=NP) exponential in the number of back-references (one measure of "size of the pattern"), in the general non-lucky cases of patterns.