HN
Hacker News
Top
New
Best
Ask
Show
Jobs
Comment by DmitryOlshansky | Hacker News Reader
Parent
Full thread
DmitryOlshansky
·
Running NFA is O(nm) not NP.
View on HN
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)
Reply on news.ycombinator.com