Even Thompson didn't use the linear time algorithm that's named after him in Ed and Grep. The Python and Perl implementations were inspired by Henry Spencer's regex, which was in turn reimplementing Thompson's backtracking implementations.
Are you sure it was Thompson who added backtracking to grep? Note also that the POSIX standard intentionally omits backtracking regex. It is a shame that others have not deprecated them.
We're talking about backtracking and not back references, right? The original implementations of Ed and Grep in Unix did backtracking, not back references.
Oops I mean't back references, since that is the problem feature (that requires backtracking).