[onan_barbarian]

This result has always been a bit of a head-scratcher for me, in that it seems to require that we increase the pattern size (specifically, the number of back-references). While the result is correct, it seems to run counter to common usage of regular expressions, where the regular expression is fixed and the interest is generally in how fast a given regular expression runs over N bytes of input data.

It feels a bit like informing people that comparing two integers is O(N) because maybe the integers are bignums with N bits each; true, but counter to common usage.

[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.

[onan_barbarian]

This seems plausible, but is the inverse of the traditional expectation of what grows and what stays the same. I refer only to a pragmatic experience of regex implementation (as opposed to a theoretical refutation of the point) - the size of the pattern is typically a constant and the metric of interest is usually the difficulty of scanning a fixed pattern over an arbitrary and increasing-sized input buffer with worst case input.