wiki_research

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

up (338B)

      1 # UP
      2 
      3 https://complexityzoo.net/Complexity_Zoo:U#up
      4 
      5 [unambiguous] [nondeterministic] [ptime], i.e., there is a [nondeterministic_ptime_turing_machine] such that:
      6 
      7 - on negative instances, all [runs] are rejecting
      8 - on positive instances, exactly one [run] accepts
      9 
     10 Generalization: [FewP]
     11 
     12 Up: [nptime], [unambiguity], [complexity_class]