wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

bringmann2024nfa (475B)

      1 # bringmann2024nfa
      2 
      3 [hardness_hypothesis] for [NFA_acceptance] on [dense_NFA]: [NFA_acceptance_hypothesis]
      4 - Implies hardness for any asymptotic regime of the number of transitions
      5 
      6 Talks about:
      7 - [context_free_language_reachability]
      8 - [word_break_problem]
      9 
     10 Their hardness hypothesis implies the [OMv_hypothesis]
     11 
     12 The question of whether a better algorithm can be found than the known ones was posed in [potechin2020lengths]
     13 
     14 Up: [academic_paper]
     15 
     16 See also: [Karl_bringmann]