wiki_research

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

nptime (377B)

      1 # NP
      2 
      3 definition:
      4 - via [nondeterministic] [ptime] [turing_machine]
      5 - via [witness]
      6 
      7 - "Berman-Hartmanis conjecture": all NP languages can be related by PTIME-computable isomorphisms
      8 
      9 subset [snp]
     10 
     11 subset [up]
     12 
     13 [npo] for [optimization_problem]
     14 
     15 Up: [complexity_class]
     16 
     17 See also: [ptime], [np_complete], [np_hard], [np_cap_conp], [conp], [nondeterministic_PTIME_Turing_machine]