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