wiki_research

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

computational_complexity (967B)

      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 - [another_solution_problem] (ASP)
     31   - [ASP_completeness]
     32 
     33 ## [database_theory]
     34 
     35 - [data_complexity]
     36 - [combined_complexity]
     37 
     38 ## Problems
     39 
     40 - [satisfiability_boolean]
     41 
     42 ## Results
     43 
     44 - [ladners_theorem]
     45 - [Rice's_theorem]
     46 
     47 ## Techniques
     48 
     49 - [log_shaving]
     50 
     51 ## Resources
     52 
     53 - [descriptive_complexity]
     54 - [lower_bounds]
     55 - [klees_measure_problem]
     56 - [complexity_zoo]
     57 
     58 Up: [theoretical_computer_science], [complexity]
     59 
     60 See also: [computability], [metacomplexity], [chaos_theory], [decidability], [lower_bounds]