np_complete (904B)
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]? 24 - it is open whether [np_complete] problems under [logspace_reduction] and [ptime_reduction] are different, cf https://en.wikipedia.org/wiki/Log-space_reduction 25 26 Up: [complete] for [nptime] 27 28 See also: [intractability], [np_hard], [conp_complete] 29 30 Aliases: NP-completeness, NP_completeness