nfa_acceptance_hypothesis (585B)
1 # NFA acceptance hypothesis 2 3 Hypothesis 2 in [bringmann2024nfa] 4 5 Implies [OMV_hypothesis] 6 7 It is the hypothesis that you cannot test acceptance of a word of length n by an [NFA] of size m in O((mn)^{1-ε}) for any ε *even for dense NFAs* 8 9 The standard [Backurs_Indyk] result says you cannot test acceptance of a word of length n by an [NFA] with m states in O((mn)^{1-ε}) for any ε 10 11 Note that for a [regular_expression] this makes no difference because a regular expression of size m can be converted to an [NFA] with O(m) states 12 13 Up: [bringmann2024nfa], [computational_hypothesis]