wiki_research

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

sharp_nfa (539B)

      1 # Sharp NFA
      2 
      3 [counting_problem] of [density_function] of [automata_nondeterministic]:
      4 - input:
      5   - [automata_nondeterministic]
      6   - a length n written in [unary]
      7 - output: cardinality of [slice] of accepted language
      8 
      9 [computational_complexity]:
     10 - [sharpp]-hard
     11   - by reduction from [sharp_satisfiability_dnf]
     12   - cf [angeliki2017complete] slide 34
     13   - cf [irwin2022complexity]
     14 - [spanl]-complete
     15 - admits a [fpras]: [arenas2021nfa]
     16 
     17 Up: [sharp_automaton], [automata_nondeterministic]
     18 
     19 See also: [sharp_dfa], [sharp_cfg]
     20 
     21 Aliases: sharpNFA