wiki_research

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

complexity_time_classes (413B)


      1 # Complexity time classes
      2 
      3 - [ptime] / [p_complete]
      4   - [linear_time], [linear_time_nearly], [linear_time_almost]
      5 - [np_intermediate], cf [ladners_theorem]
      6 - [nptime]
      7   - [conptime]
      8   - [np_cap_conp]
      9 - [exptime]
     10   - [nexptime]
     11   - [2exptime]
     12   - [TOWER]
     13 - [PP]
     14 - [PSPACE]
     15   - [pspace_complete]
     16 - [oplusP] 
     17 - [US]
     18 
     19 Up: [complexity_class], [complexity_time]
     20 
     21 Aliases: time complexity class, time complexity classes