[tgv]

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.

[DmitryOlshansky]

Running NFA is O(nm) not NP.

[tgv]

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

[benchloftbrunch]

So it is NP (in fact P)