wiki_research

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

fewp (393B)


      1 # FewP
      2 
      3 https://complexityzoo.net/Complexity_Zoo:F#fewp
      4 
      5 [Complexity_class] of [decision_problems] such that:
      6 
      7 - on negative instances, all [runs] are rejecting
      8 - on positive instances, there is an [accepting_run], and the number of [accepting_runs] is bounded by a [polynomial] as a function of the input
      9 
     10 Up: [UP], [complexity_class]
     11 
     12 See also: [polynomial_ambiguity], [Degree_of_ambiguity]