collaborators

1 paper

cs.CC2024

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds

Karl Bringmann, Allan Grønlund, Marvin Künnemann +1

We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphab…