wiki_research

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

computational_complexity (963B)

      1 # Computational complexity
      2 
      3 ## Notions
      4 
      5 - [complexity_space]
      6 - [complexity_time]
      7 
      8 - [computational_hardness]
      9 
     10 - [complexity_class]
     11 - [complexity_hierarchy]
     12 
     13 - [complexity_worst_case]
     14 - [complexity_average]
     15 - [complexity_best_case]
     16 
     17 - [complexity_generic]
     18 
     19 ## Specific classes
     20 
     21 - [complexity_random]
     22 - [complexity_class]
     23 - [logcfl] / [logdcfl]
     24 - [parameterized_complexity]
     25 - [approximation_class]
     26   - [apx]
     27 - [counting_complexity]
     28   - [sharpp]
     29 - [complexity_rectangular]
     30 
     31 ## [database_theory]
     32 
     33 - [data_complexity]
     34 - [combined_complexity]
     35 
     36 ## Problems
     37 
     38 - [satisfiability_boolean]
     39 
     40 ## Results
     41 
     42 - [ladners_theorem]
     43 - [complexity_zoo]
     44 
     45 ## Techniques
     46 
     47 - [log_shaving]
     48 
     49 ## Resources
     50 
     51 - valeurs possibles sur wikipedia: en.wikipedia.org/wiki/Time_complexity
     52 - [descriptive_complexity]
     53 - [lower_bounds]
     54 - [klees_measure_problem]
     55 
     56 Up: [theoretical_computer_science], [complexity]
     57 
     58 See also: [computability], [metacomplexity], [chaos_theory], [decidability], [lower_bounds]