Hacker News Reader

The blow up is exponential for carefully crafted academical regular expressions.

im practice is a good idea to build a DFA from your regex, up front (re2) or lazily (ripgrep)

No, because you can compute the optimal automaton (as in least number of states) that recognizes the same language: https://en.wikipedia.org/wiki/DFA_minimization

And there are language families where minimal DFA is still exponentially large compared to NFA.

Depends on what you mean by that. You can convert every NFA into a DFA. That's a NP complete (IIRC), but running the DFA is O(n). Running the NFA without converting it is also NP complete. One isn't better than the other, but the costs vary for different expressions and usages.

Running NFA is O(nm) not NP.

Sorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.

So it is NP (in fact P)