4 ms·
Running NFA is O(nm) not NP.
by DmitryOlshansky 5mo ago
Running NFA is O(nm) not NP.
- benchloftbrunch 5mo agoSo it is NP (in fact P)
- tgv 5mo agoSorry, you're right. Capturing worst case was much more expensive, I believe, but I'm no longer sure.