np_hard (543B)
1 # NP-hard 2 3 at least as hard as the hardest [computational_problem]s in [nptime] 4 - admits a [ptime_reduction] from any [nptime] problem 5 - subtlety about which type of reduction is allowed, e.g., [many_one_reduction] vs [turing_reduction] 6 - usual notion is [many_one_reduction] 7 - with [turing_reduction], the difference between [np] and [conp] disappears 8 - https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc 9 10 See also: [nptime], [computational_hardness] 11 12 Up: [computational_complexity]