wiki_research

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

up (414B)

      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 Generalizations:
     11 - [FewP]
     12 - [US]
     13 
     14 [Complement]: [coUP]
     15 
     16 Up: [nptime], [unambiguous_computation], [complexity_class]
     17 
     18 See also: [unambiguous_sigma2]