There is a persistent meme out there that matching regular expressions with back-references is NP-Hard. There is a post about this and the claim is repeated by Russ Cox so this is now part of received wisdom. None of these claims are false; they just don’t apply to regular expression matching in the sense that… Continue reading Question: Is matching fixed regexes with Back-references in P?→
