Hacker News new | ask | show | jobs
by DmitryOlshansky 33 days ago
Running NFA is O(nm) not NP.
2 comments
tgv 33 days ago
Sorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.
link
benchloftbrunch 33 days ago
So it is NP (in fact P)
link