wiki_research

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

np_complete (782B)


      1 # NP-complete
      2 
      3 https://en.wikipedia.org/wiki/NP-completeness
      4 
      5 Problem which is in [nptime] and [np_hard]
      6 
      7 - problems:
      8   - [3_partition]
      9   - [bin_packing]
     10   - [3_dimensional_matching]
     11   - [knapsack]
     12   - [subset_sum] mais [pseudo_polynomial_time] algorithm
     13   - [hitting_set]
     14   - https://en.wikipedia.org/wiki/List_of_NP-complete_problems
     15   - [garey_johnson]
     16   - 1972: the first 21 NP-complete problems of Karp
     17   - [minimum_vertex_cover]
     18   - [maximum_independent_set]
     19 
     20 weakly NP-complete ou [strongly_np_complete] depending on whether there exist
     21 [pseudo_polynomial_time] algorithms
     22 
     23 different notions of [reduction]: cf [np_definition_reductions]
     24 
     25 Up: [completeness] for [nptime]
     26 
     27 See also: [intractability], [np_hard], [conp_complete]
     28 
     29 Aliases: NP-completeness, NP_completeness, NPc