wiki_research

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

complexity_time_classes (460B)

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